Manuscript ID : 13991205262338 Visit : 4314 Page: 13 - 24

Article Type: Original Research

Improving Register File Access Latency Tolerance in GPUs by Value Reproduction

Subject Areas : electrical and computer engineering

Rahil Barati ^{1
*} , Mohammad Sadrosadati ² , حمید سربازی آزاد ³

1 - Sharif University of Technology
2 -
3 -

Received: 2021-02-23 Accepted : 2022-02-27 Published : 2022-06-20

Keywords: GPUs, register file, value re-production, execution units,

Abstract :

Large register files reduce the performance and energy overhead of memory accesses by improving the thread-level parallelism and reducing the number of data movements from the off-chip memory. Recently, the latency-tolerant register file (LTRF) is proposed to enable high-capacity register files with low power and area cost. LTRF is a two-level register file in which the first level is a small fast register cache, and the second level is a large slow main register file. LTRF uses a near-perfect register prefetching mechanism that warp registers are prefetched from the main register file to the register file cache before scheduling the warp and hiding the register prefetching latency by the execution of other active warps. LTRF specifies the working set of the warps by partitioning the control flow graph into several prefetch subgraphs, called register-interval. LTRF imposes some performance overhead due to warp stall during the register prefetching. Reducing the number of register-intervals can greatly mitigate this overhead, and improve the effectiveness of LTRF. A register-interval is a subgraph of the control flow graph (CFG) where it has to be a single-entry subgraph with a limited number of registers. We observe that the second constrain contributes more in reducing the size of register-intervals. Increasing the number of registers inside the register-interval cannot address this problem as it imposes huge performance and power overhead during the register prefetching process. In this paper, we propose a register-interval-aware re-production mechanism at compile-time to increase register-interval size without increasing the number of registers inside it. Our experimental results show that our proposal improves the effectiveness of LTRF by 29%, and LTRF’s performance by about 18% (about 30% improvement over baseline GPU architecture). Moreover, our proposal reduces GPU energy and power consumption by respectively 38% and 15%, on average.

References:

[1] A. Sethia and S. Mahlke, "Equalizer: dynamic tuning of gpu resources for efficient execution," in Proc. of the IEEE/ACM 47th Annual Int. Symp. on Microarchitecture, pp. 647-658, Cambridge, UK, 13-17 Dec. 2014.
[2] T. D. Han and T. S. Abdelrahman, "hiCUDA: high-level GPGPU programming," IEEE Trans. on Parallel and Distributed Systems, vol. 22, no. 1, pp. 78-90, Jan. 2011.
[3] NVIDIA Corporation. CUDA Programming Guide, V4.0.
[4] NVIDIA Corporation. CUDA Toolkit, 2012. Version 4.2, http://developer.nvidia.com/cuda/cuda-downloads. Sep. 2012.
[5] J. Lee, N. Lakshminarayana, H. Kim, and R. Vuduc, "Many-thread aware prefetching mechanisms for GPGPU applications," in Proc. IEEE/ACM of the 43th Annual Int. Symp. on Microarchitecture, pp. 213-224, Atlanta, GA, USA, 4-8 Dec. 2010.
[6] A. Jog, O. Kayiran, A. Mishra, M. T. Kandemir, O. Mutlu, R. Iyer, and C. R. Das, "Orchestrated scheduling and prefetching for GPGPUs," ACM SIGARCH Computer Architecture News, vol. 41, no. 3, pp. 332-343, Jun. 2013.
[7] A. Jog, O. Kayiran, N. Chidambaram, A. Mishra, M. T. Kandemir, O. Mutlu, R. Iyer, and C. R. Das, "OWL: cooperative thread array aware scheduling techniques for improving GPGPU performance," ACM SIGARCH Computer Architecture News, vol. 41, no. 1, pp. 395-406, Mar. 2013.
[8] A. Sethia, G. Dasika, M. Samadi, and S. Mahlke, "APOGEE: adaptive prefetching on GPUs for energy efficiency," in Proc. of the IEEE 22nd Int. Conf. on Parallel Architectures and Compilation Techniques, pp. 73-82, Edinburgh, UK, 7-11 Sept. 2013.
[9] H. Jeon, G. S. Ravi, N. S. Kim, and M. Annavaram, "GPU register file virtualization," in Proc. IEEE/ACM of the 48th Annual Int. Symp. on Microarchitecture, pp. 420-432, Waikiki, HI, USA, 5-9 Dec. 2015.
[10] M. Abdel-Majeed and M. Annavaram, "Warped register file: a power efficient register file for GPGPUs," in Proc. IEEE 19th Int. Symp. on High Performance Computer Architecture, pp. 412-423, Shenzhen, China, 23-27, Feb. 2013.
[11] S. Lee, K. Kim, G. Koo, H. Jeon, W. W. Ro, and M. Annavaram, "Warped-compression: enabling power efficient GPUs through register compression," ACM SIGARCH Computer Architecture News, vol. 43, no. 3, pp. 502-514, Jun. 2015.
[12] C. Hsiao, S. Chu, and C. Hsieh, "An adaptive thread scheduling mechanism with low-power register file for mobile GPUs," IEEE Trans. on Multimedia, vol. 16, no. 1, pp. 60-67, Sept. 2014.
[13] N. Jing, J. Wang, F. Fan, W. Yu, L. Jiang, C. Li, and X. Liang, "Cache-emulated registerfile: an integrated on-chip memory architecture for high performance gpgpus," in Proc. IEEE/ACM of the 49th Annual Int. Symp. on Microarchitecture, 12 pp., Taipei, Taiwan, 10-15?, Oct. 2016.
[14] H. Asghari Esfeden, A. A. Abdolrashidi, S. Rahman, D. Wong, and N. Abu-Ghazaleh, "BOW: breathing operand windows to exploit bypassing in GPUs," in Proc. IEEE/ACM of the 53th Annual Int. Symp. on Microarchitecture, pp. 996-1008, Athens, Greece, 17-21 Oct. 2020.
[15] F. Khorasani, H. A. Esfeden, A. Farmahini-Farahani, N. Jayasena, and V. Sarkar, "Regmutex: inter-warp gpu register time-sharing," in Proc. of the 45th Annual Int. Symp. on Computer Architecture, pp. 816-828, Providence, RI, USA, 13-17 Apr. 2018.
[16] H. Asghari Esfeden, F. Khorasani, H. Jeon, D. Wong, and N. Abu-Ghazaleh, "CORF: coalescing operand register file for GPUs," in Proc. of the 24th Int. Conf. on Architectural Support for Programming Languages and Operating Systems, pp. 701-714, Boston, MA, USA, 14-17 Oct. 2019.
[17] J. Kloosterman, et al., "Regless: just-in-time operand staging for gpus," in Proc. IEEE/ACM of the 50th Annual Int. Symp. on Microarchitecture, pp. 151-164, Boston, MA, USA, 14-17, Oct. 2017.
[18] M. Sadrosadati, A. Mirhosseini, S. B. Ehsani, H. Sarbazi-Azad, M. Drumond, B. Falsafi, R. Ausavarungnirun, and O. Mutlu, "Ltrf: enabling high-capacity register files for gpus via hardware/software cooperative register prefetching," in Proc. of the 23rd Int. Conf. on Architectural Support for Programming Languages and Operating Systems, pp. 489-502, Williamsburg, VA, USA, 24-18 Mar. 2018.
[19] J. E. Lindholm, M. Y. Siu, S. S. Moy, S. Liu, and J. R. Nickolls, Simulating Multiported Memories Using Lower Port Count Memories, US Patent 7,339,592, 2008.
[20] LTRF Register-Interval-Algorithm, https://github.com/CMU-SAFARI/Register-Interval, 2018.
[21] A. Bakhoda, G. L. Yuan, W. W. Fung, H. Wong, and T. M. Aamodt, "Analyzing cuda workloads using a detailed gpu simulator," ISPASS. in Proc. IEEE Int. Symp. on Performance Analysis of Systems and Software,, pp. 163-174, Boston, MA, USA, 26-28 Apr. 2009.
[22] S. Che, et al., "Rodinia: a benchmark suite for heterogeneous computing," in Proc. IEEE Int. Symp. on Workload Characterization, pp. 44-54, Austin, TX, USA, 4-6 Oct. 2009.
[23] J. A. Stratton, et al., "Parboil: a revised benchmark suite for scientific and commercial throughput computing," Center for Reliable and High-Performance Computing, vol. 127, p. 27, Mar. 2012.
[24] R. Venkatesan, S. G. Ramasubramanian, S. Venkataramani, K. Roy, and A. Raghunathan, "Stag: spintronic-tape architecture for GPGPU cache hierarchies," in Proc. IEEE Int. Symp. on Computer Architecture, pp. 253-264, Minneapolis, MN, USA, 14-18 Jun. 2014.
[25] V. Narasiman, M. Shebanow, C. J. Lee, R. Miftakhutdinov, O. Mutlu, and Y. N. Patt, "Improving gpu performance via large warps and two-level warp scheduling," in Proc. IEEE/ACM of the 44th Annual Int. Symp. on Microarchitecture, pp. 308-317, Porto Alegre, Brazil, 3-7, Dec. 2011.

Full-Text:

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

مقاله پژوهشی

بهبود تحمل‌پذیری تأخیر پوشه ثبات در پردازنده‌های
گرافیکی به کمک بازتولید مقادیر میانی

راحیل براتی، سیدمحمد صدرالساداتی و حمید سربازی آزاد

چكیده: پوشه‌ ثبات‌ بزرگ در پردازنده‌های گرافیکی با بهبود موازات سطح نخ، باعث کاهش دسترسی به حافظه‌ می‌شود. قبلاً برای افزایش ظرفیت پوشه‌ ثبات با سربار توان و مساحت قابل قبول، روش LTRF ارائه شده است. معماری پوشه‌ ثبات LTRF دوسطحی است که از یک حافظه نهان ثبات و یک پوشه‌ ثبات اصلی استفاده می‌کند. ثبات‌های کلاف‌ها قبل از اجرای یک کلاف به حافظه نهان ثبات پیش‌واکشی می‌شوند. برای پیش‌واکشی ثبات‌ها، گراف کنترل جریان برنامه در سطح مترجم به زیرگراف‌هایی به نام بازه‌ثبات تقسیم می‌شود. یکی از سربار‌های روش LTRF انجام عمل پیش‌واکشی ثبات و تحمیل بیکاری کلاف در طول مدت پیش‌واکشی است که کاهش تعداد بازه‌ثبات به میزان چشم‌گیری این سربار را کاهش می‌دهد. اما تعداد ثبات‌ قابل استفاده در هر بازه‌ثبات محدود است و افزایش این تعداد در بازه‌ثبات منجر به افزایش ترافیک پیش‌واکشی و ظرفیت حافظه نهان می‌گردد که راه حل مناسبی برای کاهش تعداد بازه‌ثبات‌ها نیست. در این پژوهش به کمک بازتولید مقادیر میانی در زمان ترجمه سعی در کاهش تعداد ثبات‌های مورد نیاز در هر بازه‌ثبات داریم. نتایج شبیه‌سازی نشان می‌دهند که روش پیشنهادی ما، میزان تحمل‌پذیری تأخیر دسترسی به پوشه ثبات در روش LTRF را به میزان 29 درصد بهبود می‌بخشد. همچنین با
به کار‌گیری یک پوشه ثبات سلول‌های حافظه DWM، معماری پیشنهادی قادر است که کارایی پردازنده گرافیکی مجهز به LTRF را به طور میانگین 18 درصد (حدود 30 درصد نسبت به معماری پردازنده گرافیکی پایه) افزایش دهد و این
در حالی است که مقادیر انرژی و توان مصرفی به میزان 38 و 15 درصد کاهش می‌یابد.

کلیدواژه: پردازنده‌هاي گرافيكي، پوشه ثبات، بازتوليد مقادير، واحدهاي اجرايي.

1- مقدمه

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

ویژگی معماری پردازنده‌های گرافیکی این است که با آماده نگه داشتن تعداد بسیار زیادی نخ برای اجرا، سعی در پنهان‌سازی تأخیر دسترسی به حافظه دارند [1] تا [4]. بنابراین اگر برنامه به گونه‌ای باشد که به اندازه کافی نخ فعال در حین اجرا داشته باشد، هنگام رخداد دسترسی به حافظه، فرایند اجرا به یک نخ دیگر منتقل می‌شود تا تأخیر دسترسی به حافظه به کمک زمان اجرای سایر نخ‌ها پنهان شود. اما در تحقیقات گذشته نشان داده شده که تعداد نخ‌های آماده اجرا برای بارهای کاری عام‌منظوره در پردازنده گرافیکی به اندازه‌ای نیست که بتواند تأخیر دسترسی به حافظه را به صورت مناسب پنهان کند. در این راستا، عوامل متعددی از قبیل تعداد مجاز بلوک نخ، ظرفیت حافظه مشترک و ظرفیت پوشه ثبات منجر به کاهش تعداد نخ‌های آماده اجرا می‌شوند [1] و [5] تا [8].

مهم‌ترین عامل محدودکننده تعداد نخ‌های آماده اجرا، ظرفیت محدود پوشه ثبات است [9] تا [11]. از آنجا که هر نخ باید ثبات‌های اختصاصی داشته باشد تا فرایند تعویض محتوا به سرعت انجام گیرد، پردازنده‌های گرافیکی به تعداد ثبات‌های بسیار زیادی نیاز دارند [9] تا [12]. متأسفانه به دلیل مساحت زیاد و توان مصرفی چشم‌گیر پوشه ثبات که از سلول‌های SRAM ساخته شده است، ظرفیت کنونی آن بسیار کمتر از ظرفیت
مورد انتظار برای جلوگیری از محدودشدن آن برای تعداد نخ‌های آماده اجرا است.

افزایش حجم حافظه‌های روی تراشه از جمله افزایش ظرفیت پوشه ثبات با هدف بهبود کارایی، بدون در نظر گرفتن محدودیت‌های مساحت
و توان مصرفی امکان‌پذیر نیست [13]. پژوهش‌های زیادی‌ به ارائه راهکارهایی با رویکرد کاهش توان مصرفی پوشه‌ ثبات پرداخته‌اند [13] تا [16]. از جمله راهکارهای پیشنهادشده می‌توان به اضافه‌کردن یک حافظه ‌نهان به ساختار پوشه ثبات و یکپارچه‌سازی حافظه‌های روی تراشه و اختصاص آن به هر بخش به شکل ایستا یا پویا اشاره کرد [13]. در سال 2019 روشی به نام CORF ارائه شد که با کمک تکنیک‌های زمان ترجمه به ادغام چند دسترسی به پوشه ثبات می‌پردازد. این روش با کاهش دفعات دسترسی فیزیکی به پوشه ثبات، انرژی مصرفی را کاهش می‌دهد و با ادغام چندین خواندن، فشار روی پوشه ثبات و احتمال تداخل بین بانک‌ها در پوشه ثبات را کم می‌کند [16]. پژوهش دیگری با نام

شکل 1: معماری پایه پوشه ثبات در پردازنده‌های گرافیکی [19].

BOW با ایجاد تغییراتی در واحد جمع‌آوری عملوندها⁵ و اضافه‌کردن بافر، از خواندن و نوشتن‌های غیر ضروری بر پوشه ثبات جلوگیری می‌کند. در روش BOW بهینه‌سازی در زمان ترجمه، در تصمیم‌گیری برای نوشتن یک عملوند در پوشه ثبات یا صرفاً نوشتن آن در بافر مؤثر خواهد بود [14]. در سال‌های اخیر، توجه به تکنیک‌های زمان ترجمه برای استفاده حداکثری از ظرفیت پوشه ثبات و یا تحمل‌پذیر ساختن سربارها، مورد توجه بیشتری قرار گرفته که از این میان می‌توان به روش RegMutex اشاره کرد [15]. در این روش در زمان ترجمه، پوشه ثبات به دو بخش مجموعه ثبات‌های پایه و مجموعه‌ ثبات‌های گسترده تقسیم می‌شود. در زمان اجرا، ثبات‌های متعلق به مجموعه ثبات‌های گسترده میان کلاف‌ها به طور مشترک استفاده می‌شوند [15]. البته روش‌های اشاره‌شده در بالا به موضوع سربار مساحت برای افزایش ظرفیت پوشه ثبات در کنار توان مصرفی به خوبی نپرداخته‌اند و بهبود اشاره‌شده در توان مصرفی پوشه ثبات‌های پیشنهادی در بهترین حالت حدود 50 درصد گزارش شده است که می‌تواند برای طراحی یک پوشه ثبات با ظرفیت 5/1 تا 2 برابری مورد استفاده قرار گیرد. با توجه به تحلیل‌های صورت‌گرفته (تأثیر افزایش ظرفیت پوشه ثبات بر کارایی در شکل 3 دیده می‌شود که این مقایسه با معماری پایه پردازنده گرافیکی صورت گرفته است)، این میزان افزایش در حجم پوشه ثبات کافی نبوده و نیاز به پوشه ثبات بسیار بزرگ‌تر همچنان وجود دارد.

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

روش ⁶LTRF [18] برای افزایش ظرفیت پوشه‌ ثبات با سربار توان و مساحت قابل قبول ارائه شده است. معماری پوشه‌ ثبات LTRF از یک حافظه نهان ثبات و یک پوشه‌ ثبات اصلی استفاده می‌کند. ثبات‌های کلاف‌ها قبل از اجرای یک کلاف از پوشه‌ ثبات اصلی به حافظه نهان ثبات پیش‌واکشی می‌شوند و تأخیر پیش‌واکشی ثبات به کمک زمان اجرای سایر کلاف‌ها پنهان می‌شود. برای پیش‌واکشی ثبات‌ها، گراف کنترل جریان برنامه در سطح مترجم به زیرگراف‌هایی به نام بازه‌ثبات تقسیم می‌شود.

یکی از سربار‌های روش LTRF بیکاری کلاف در طول مدت پیش‌واکشی است که با کاهش تعداد بازه‌ثبات‌ها می‌توان این سربار را کاهش داد. هنگام تقسیم گراف کنترل جریان برنامه به بازه‌ثبات‌ها، 2 محدودیت اصلی در نظر گرفته می‌شود: 1) این که هر بازه‌ثبات، زیرگرافی است که تنها یک ورودی دارد و 2) این که بیشینه تعداد ثبات‌ در هر بازه‌ثبات محدود است. بررسی‌ها نشان می‌دهند که عامل محدودکننده اصلی برای بزرگ‌ترشدن بازه‌ثبات و کمترشدن تعداد بازه‌ثبات‌ها، اغلب عامل دوم است. محدودیت ترافیک پیش‌واکشی و حجم حافظه نهان، اجازه افزایش تعداد ثبات‌های مجاز در بازه‌ثبات‌ها را نمی‌دهد.

این پژوهش با هدف کاهش سربارهای پیش‌واکشی و بیکاری کلاف‌ها در طول زمان پیش‌واکشی با استفاده از بازتولید مقادیر میانی ارائه شده است. در بخش اول با استفاده از یک روش زمان ترجمه، به محاسبه مجدد ثبات‌ها با توجه به مقادیر اولیه آنها می‌پردازیم. بازتولید این مقادیر با توجه به بازه زندگی هر ثبات و وجود عملوندهای مورد نیاز بازتولید صورت می‌گیرد. بازتولید مقادیر میانی در روش LTRF باعث بزرگ‌ترشدن اندازه بازه‌ثبات، بیشترشدن تعداد دستورات قابل اجرا در یک بازه‌ثبات و در نتیجه کاهش سربار پیش‌واکشی و نیز کاهش سربار بیکاری کلاف در طول مدت پیش‌واکشی می‌شود. مزیت این روش آن است که بدون ایجاد تغییر در تعداد مجاز ثبات‌ها و بدون افزایش ترافیک پیش‌واکشی و تغییر در ظرفیت حافظه نهان، می‌توان بازه‌ثبات‌های بزرگ‌تری داشت. بهره‌گیری از این روش در معماری LTRF باعث بهبود عملکرد روش LTRF و افزایش میزان تحمل‌پذیری تأخیر دسترسی به پوشه ثبات آن گردیده است. نتایج شبیه‌سازی ما نشان می‌دهد که تحمل‌پذیری تأخیر دسترسی به پوشه ثبات روش LTRF به میزان ۲۹ درصد با به کارگیری روش پیشنهادی بهبود می‌یابد.

در ادامه از نتایج روش پیشنهادی (تحمل‌پذیری تأخیر پوشه ثبات) استفاده می‌کنیم تا کارایی و انرژی پردازنده گرافیکی را بهبود دهیم. آزمایش‌های ما با پیکربندی‌های گوناگون برای تعداد کلاف و تعداد بازه‌ثبات متفاوت، نشان می‌دهند که طراحی صورت‌گرفته در بخش قبل، با پیکربندی 4 کلاف فعال و حداکثر 12 ثبات در هر بازه‌ثبات، تحمل تأخیر پوشه ثبات تا 6 برابر ظرفیت معماری پردازنده گرافیکی پایه را دارد. نتایج شبیه‌سازی با پیکربندی جدید، بهبود 38 درصدی انرژی پردازنده گرافیکی و بهبود 18 درصدی کارایی را به همراه دارد.

1-1 معماری پوشه ثبات

شکل 1 معماری متداول پوشه‌ ثبات در چند پردازنده جریانی پردازنده‌های گرافیکی را نشان می‌دهد [19]. ظرفیت پوشه‌ ثبات در پردازند‌های گرافیکی در حدود چندین مگابایت است که برای اجرای هم‌زمان تعداد فراوان نخ‌ها ضروری است. به عنوان مثال، ظرفیت پوشه‌ ثبات در پردازنده گرافیکی مدل GP 100 در حدود 14 مگابایت است. هر پوشه ثبات متشکل از تعدادی بانک می‌باشد و به منظور فراهم‌کردن پهنای باند مناسب، تعداد بانک بیشتری در پوشه‌ ثبات پردازنده‌های

(الف)

(ب)

شکل 2: مقایسه تأثیر عوامل گوناگون در محدود‌سازی موازات سطح نخ،‌ (الف) نسل فرمی و (ب) نسل پاسکال.

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

1-2 موازات سطح نخ

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

1) بیشینه تعداد بلوک نخ در چند پردازنده جریانی

2) ظرفیت حافظه مشترک

3) ظرفیت پوشه ثبات

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

شکل ۲ تأثیر عوامل گوناگون را در محدودکردن موازات سطح نخ در دو نسل پردازنده گرافیکی، فرمی (سال ۲۰۰۹) و پاسکال (سال ۲۰۱۶) نشان می‌دهد. همان طور که مشاهده می‌شود در نسل‌های کنونی، ظرفیت پوشه‌ ثبات سهم ۸۳ درصدی در محدودکردن موازات سطح نخ دارد و در نتیجه، مهم‌ترین عامل محدودکردن موازات سطح نخ ظرفیت پوشه ثبات است. معماری LTRF برای غلبه بر این مشکل طراحی شده که این معماری، امکان ساخت پوشه‌ ثبات‌های بزرگ و با توان مصرفی
و مساحت کم را ایجاد می‌کند، اما معایبی دارد که در بخش بعد به آن می‌پردازیم.

2- انگیزه

پوشه‌ ثبات بزرگ می‌تواند در بهبود کارایی پردازنده‌های گرافیکی مؤثر باشد. شکل ۳ کارایی پردازنده گرافیکی را بعد از افزایش ظرفیت پوشه‌

شکل 3: تأثیر افزایش ظرفیت پوشه ثبات روی کارایی پردازنده‌های گرافیکی در حالت ایده‌آل نسبت به معماری پایه پردازنده گرافیکی.

شکل 4: تأثیر افزایش تعداد مجاز ثبات‌ها در بازه‌ثبات بر میانگین تعداد بازه‌ثبات‌ها.

ثبات از ۲۵۶ کیلوبایت به ۵/۱ مگابایت نشان می‌دهد. در واقعیت افزایش ظرفیت پوشه‌ ثبات منجر به افزایش تأخیر دسترسی به پوشه‌ ثبات می‌شود که می‌تواند کارایی را کاهش دهد. اما در این آزمایش در حالت ایده‌آل فرض شده که تأخیر دسترسی افزایش نیافته است. روش LTRF به عنوان یک پوشه ثبات سلسله‌مراتبی با قابلیت تحمل تأخیر دسترسی ارائه گردیده است.

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

هر بازه‌ثبات یک زیرگراف از گراف کنترل جریان برنامه است که دو ویژگی مهم دارد: ۱) تنها یک نقطه ورودی کنترل جریان دارد و ۲) تعداد ثبات‌های داخل آن از بیشینه تعداد ثبات مشخص‌شده برای هر کلاف در حافظه نهان پوشه‌ ثبات کمتر یا مساوی است. در این بخش ابتدا بررسی می‌شود که کدام یک از ویژگی‌های بازه‌ثبات، در محدودکردن بازه‌ثبات تأثیر بیشتری می‌گذارد. برای این منظور، تعداد مجاز ثبات‌ها در یک بازه‌ثبات از ۱۶ تا ۲۵۶ افزایش داده شده و میانگین تعداد بازه‌ثبات‌ها‌ برای هر حالت بین بارهای کاری گوناگون محاسبه گردیده است.

در شکل 4، تأثیر افزایش تعداد مجاز ثبات‌ها در یک بازه‌ثبات بر تعداد بازه‌ثبات‌ها، در دو حالت بدون قانونِ CFG (خط‌چین نارنجی) و با قانونِ CFG (ممتد آبی) مقایسه شده‌اند. در این شکل نتایج هنجار‌سازی شده به تعداد پایه بازه‌ثبات گزارش شده است. همان طور که مشاهده می‌شود، افزایش تعداد ثبات‌ها از ۱۶ به ۲۵۶، میانگین تعداد بازه‌ثبات‌ را به میزان ۹۸ درصد کاهش داده است. کاهش تعداد بازه‌ثبات‌ها در این آزمایش

شکل 5: مقایسه تأثیر افزایش تعداد مجاز ثبات در بازه‌ثبات روش LTRF بر میزان پنهان‌سازی تأخیر دسترسی به پوشه ثبات در دو حالت ایده‌آل و با سربار واقعی.

نشان‌دهنده کاهش محدودیت ساخته‌شدن بازه‌ثبات و امکان ترکیب‌شدن بیشتر بازه‌ثبات‌ها با یکدیگر است.

سپس آزمایش با حذف اثر ویژگی کنترل جریانی تکرار شده (بدون قانونِ CFG) و میانگین تعداد بازه‌ثبات‌ها برای مقادیر گوناگون ثبات‌ها محاسبه گردیده و نتایج به تعداد پایه بازه‌ثبات، هنجار‌سازی شده است. مشاهده می‌شود که حذف قانون شماره ۱ تأثیر چندانی در کاهش تعداد بازه‌ثبات‌ها ندارد و تعداد بازه‌ثبات‌ها با حالت قبل تقریباً یکسان است. همچنین با افزایش تعداد مجاز ثبات‌ها در بازه‌ثبات، تأثیر حذف قانون
در سطح گراف کنترل جریان کاهش می‌یابد. نتیجه می‌گیریم که تعداد محدود ثبات‌ها در بازه‌ثبات، نقشی کلیدی را در تعیین تعداد بازه‌ثبات‌ها ایفا می‌کند.

کاهش تعداد بازه‌ثبات‌ها (یا افزایش اندازه بازه‌ثبات‌ها) می‌تواند مزایای زیر را به ارمغان بیاورد:

• تعداد دستور‌العمل‌های ایستا و پویا را در بازه‌ثبات افزایش می‌دهد که منجر به افزایش قدرت مکانیزم LTRF در پنهان‌سازی تأخیر پیش‌واکشی ثبات‌ها می‌گردد.

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

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

در این پژوهش تصمیم داریم که با کاهش تعداد ثبات‌های مصرفی در بازه‌ثبات به کمک روش بازتولید مقادیر میانی، تعداد بازه‌ثبات‌ها را بدون افزایش بیشینه تعداد مجاز ثبات، کاهش دهیم. پژوهش‌های گذشته نشان می‌دهند که واحد‌های اجرایی در پردازنده‌های گرافیکی به میزان قابل توجهی بیکاری دارند که می‌توان از پهنای باند پردازشی به هدر رفته برای بازتولید مقادیر میانی بهره برد.

3- روش پیشنهادی

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

• اول امکان محاسبه مجدد یک ثبات‌ از طریق مقادیر پایه آن بررسی می‌گردد که این شرط با توجه به بازه زندگی هر ثبات و وجود عملوندهای مورد نیاز آن بررسی می‌شود. بازه زندگی هر ثبات از ابتدای تعریف‌شدن آن یعنی دستورالعمل نوشته‌شدن در ثبات آغاز می‌گردد و تا آخرین باری که بدون تغییر خوانده می‌شود، ادامه می‌یابد. وجود عملوند‌ها را این گونه تعریف می‌کنیم: قطع‌نشدن بازه زندگی عملوند‌ها از محل تعریف‌شدن ثبات مورد نظر تا آخرین باری که استفاده شده است.

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

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

در ادامه در بخش 3-1 مفاهیم تئوری ساخت بازه‌ثبات در روش LTRF توضیح داده می‌شود و در بخش 3-2 شبه‌کد دومرحله‌ای روش پیشنهادی و توضیحات مربوط به آن آمده است.

3-1 نحوه ساخت بازه‌ثبات‌ها

به علت وقفه ایجادشده در ابتدای زیرگراف پیش‌واکشی، دستورات مربوط به پیش‌واکشی ثبات تأخیر زیادی دارند که این تأخیر می‌تواند منجر به کاهش کارایی پردازنده گرافیکی گردد و بنابراین استفاده از دستورالعمل‌های پیش‌واکشی باید بسیار محدود باشند. در روش LTRF گراف کنترل جریان برنامه‌های پردازند‌ه گرافیکی به تعدادی بازه‌ثبات تقسیم می‌‌شود. بازه‌ثبات‌، زیرگرافی از گراف کنترل جریان با دو شرط است: ۱) تنها یک ورودی کنترل جریان دارد و ۲) تعداد ثبات‌های داخل آن از بیشینه تعداد ثبات مشخص‌‌شده برای هر کلاف در حافظه نهان پوشه ثبات، کمتر یا مساوی است. مهم‌ترین تفاوت بازه‌‌ثبات با ساختارهای مشابهی که در کارهای گذشته ارائه شده است این است که در بازه‌ثبات ساختارهای پیچیده کنترل جریان (مانند پرش‌های برگشتی⁸) مجاز بوده و این ساختارها منجر به اتمام بازه‌ثبات نمی‌شوند. به عبارت دیگر، بازه‌ثبات محدودیت‌های بسیار کمتری نسبت به ساختارهای گذشته دارد.

کاهش محدودیت‌ها در ساخت بازه‌ثبات 2 سود مهم به ارمغان می‌آورد: ۱) افزایش تعداد دستورالعمل‌های ایستا در بازه‌ثبات که منجر به کاهش تعداد دستورالعمل‌های پیش‌واکشی می‌گردد و ۲) مجازبودن پرش‌های برگشت در بازه‌ثبات باعث می‌شود تا حلقه‌ها در بازه‌ثبات جای گرفته و

$img0$

شکل 6: ساخت بازه‌ثبات برای حلقه‌های تودرتوی ساده [18].

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

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

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

در مرحله‌ دوم با ترکیب بازه‌ثبات‌ها، گراف کنترل جریان بازه‌ثبات کاهش می‌یابد. این مرحله‌ مشابه مرحله اول کار می‌کند با این تفاوت که امکان شکستن بازه‌ثبات‌ها نیست. دو بازه‌ثبات در صورت برقراری این دو شرط با هم ترکیب می‌شوند: ۱) یکی از این بازه‌ثبات‌ها تنها از طریق دیگری قابل دسترسی باشد (یال ورودی آن تنها از دیگری باشد) و ۲) مجموعه ثبات‌های این دو بازه‌ثبات در فضای حافظه نهان پوشه ثبات جا گیرد. مرحله دوم آن قدر تکرار می‌شود تا گراف کنترل جریان بازه‌ثبات دیگر کاهش‌پذیر نباشد (هیچ کدام از بازه‌ثبات‌ها قابل ترکیب‌شدن نباشند).

همان طور که در الگوریتم ساخت بازه‌ثبات توضیح داده شده است، یک بلوک پایه تنها زمانی می‌تواند با یک بازه‌ثبات دیگر ترکیب شود که یال ورودی این بلوک پایه فقط از این بازه‌ثبات باشد. در نتیجه، یال‌های برگشتی (پرش‌های برگشتی) و حلقه‌ها همواره بازه‌ثبات جدید ایجاد می‌کنند. این ویژگی کلیدی در الگوریتم ساخت بازه‌ثبات‌ها، از آنها زیرگراف‌‌های مناسبی برای پیش‌واکشی معرفی می‌کند. در هر حلقه، به احتمال زیاد یک بازه‌ثبات برای کل حلقه (شامل‌شدن حلقه‌های داخلی) در نظر گرفته می‌شود تا برای کل حلقه تنها یک دستور پیش‌واکشی وجود داشته باشد.

شکل 6 حلقه‌های‌ تودرتو را نشان می‌‌دهد. فرض می‌کنیم که تمام ثبات‌های این گراف در حافظه نهان پوشه ثبات جای ‌گیرند. در مرحله اول الگوریتم، بلوک پایه "A" به عنوان بازه‌ثبات اول معرفی می‌گردد. بلوک پایه "B" نمی‌تواند به بازه‌ثبات اول ملحق شود زیرا یکی از ورودی‌های آن از بلوک پایه "C" است. بنابراین بلوک پایه "B" به عنوان بازه‌ثبات
دو معرفی می‌گردد. بلوک پایه "C" می‌تواند به بازه‌ثبات دو ملحق شود زیرا تنها ورودی آن از بازه‌ثبات دو است. بنابراین کل حلقه داخلی به عنوان یک بازه‌ثبات معرفی می‌شود. در این مرحله، کار مرحله اول به انتها می‌رسد. در مرحله دوم الگوریتم ساخت بازه‌ثبات‌ها، بازه‌ثبات اول به بازه‌ثبات دوم ملحق می‌گردد زیرا تنها ورودی آن از بازه‌ثبات دو است. بنابراین کل حلقه‌های تودرتو در انتها به عنوان یک بازه‌ثبات معرفی می‌شود. همان طور که قبلاً نیز اشاره شد، این ویژگی منجر به افزایش تعداد دستورالعمل‌های پویا در هر بازه‌ثبات می‌گردد.

پیاده‌سازی مرحله اول و دوم الگوریتم ساخت بازه‌ثبات‌ها به زبان CPP در آدرس [20] قرار دارد. زمان اجرای الگوریتم ساخت بازه‌ثبات برای بارهای کاری گوناگون، بسته به اندازه و پیچیدگی گراف کنترل جریان متفاوت است. در بین ۳۵ بار کاری آزمون‌شده، زمان اجرای پیاده‌سازی CPP الگوریتم ساخت بازه‌ثبات [19] به طور میانگین حدود ۲ دقیقه و به طور بیشینه حدود ۷ دقیقه است. البته این هزینه برای هر بار کاری تنها یک بار پرداخت می‌شود.

3-2 نحوه ساخت بازه‌ثبات آگاه از بازتولید مقدار میانی

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

در شروع، الگوریتم ساخت بازه‌ثبات آگاه از بازتولید نیز مانند الگوریتم روش پایه، اولین بازه‌ثبات را با قراردادن بلوک پایه ورودی می‌سازد (خط ۸ در مرحله اول الگوریتم) و در ادامه تلاش می‌کند تا بلوک‌های بعدی را به بازه‌ثبات اضافه کند. یک بلوک پایه‌ باید دو ویژگی مهم داشته باشد: ۱) مسیر ورودی بلوک پایه تنها از طریق بازه‌ثبات مورد نظر باشد و ۲) تعداد ثبات در مجموعه ثبات‌های این بلوک پایه و بازه‌ثبات مورد نظر از بیشینه تعداد مجاز ثبات در بازه‌ثبات بیشتر نباشد. بنابراین هنگام افزودن یک بلوک پایه به بازه‌ثبات قبلی، طبق الگوریتم‌ ساخت بازه‌ثبات، تعداد ثبات موجود در این ترکیب جدید با عدد ثابت مقایسه می‌گردد. در صورت

Algorithm One. Register-Interval Formation: Pass One

Input: Aplication Control Graph (CFG)

Output: Register-Interval CFG

1. Initialize

2. for each basic block: BB do

3. BB.input listempty() //List of all register cache at the

beginning of BB

4. BB.register-intervalUnknown

5. end for

6. Working-Setempty()

7. entry_blockregister-intervalnew register-interval() //Each

CFG has an entry basic block

8. Working-Setinsert (entry_block)

9. While (!Working-Set empty()) do

10. BBa basic block from Working-Set

11. TRAVERSE (BB)

12. iBB.register-interval

13. While (Basic block h for which h.register-

interval==Unknown & all of h predecessors belong to i &

union (output_list of all h predecessors).size).size()N) do

//N is maximum number of registers allowed in the register

interval

14. h.register-intervali

15. h.input_listunion (output_list of all h predecessors)

16. TRAVERSE (h)

17. end while

18. for each Sinsuccessors() do

19. if (S register-interval==Unknown) then

20. S.register-intervalnew register-interval()

21. S.input_listempty()

22. Working-Set.insert (S)

23. end if

24. end for

25. end while

26. procedure TRAVERSE (BB)

27. register_listBB.input_list

28. for each instruction in BB do

29. update register_list

30. if ((register_list.size()N) &

reproduction(N,BB)==false)) then

31. cut BB and introduce a new basic block: BB1

32. BB1.register-intervalnew register-interval()

33. BB1.input_listempty()

34. Working-Set.insert (BB1)

35. BBoutput_listregister_list //List of all registers in

the register file cache at the end of BB

36. exit

37. end if

38. end for

39. end procedure

شکل 7: مرحله اول الگوریتم ساخت بازه‌ثبات.

کوچک‌تر یا مساوی‌بودن طبق روال سابق بازه‌ثبات‌ها ساخته می‌شوند.

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

بازتولید مقادیر میانی با توجه به بازه زندگی هر ثبات و وجود عملوندهای مورد نیاز آن صورت می‌گیرد. بازه زندگی هر ثبات از ابتدای تعریف‌شدن آن یعنی دستورالعمل نوشته‌شدن در ثبات آغاز می‌گردد و تا آخرین باری که بدون تغییر خوانده می‌شود ادامه می‌یابد. وجود عملوندها

Algorithm Two. Register-Interval Formation: Pass Two

Input: Aplication Control Graph (CFG)

Output: Reduced Register-Interval CFG

1. Initialize

2. for each register-interval: i do

3. i.register-intervalUnknown

4. end for

5. Working-Setempty()

6. entry_register-interval.next_level_register-intervalnew

next_level_register-interval()

7. Working-Set.insert (entry_register-interval)

8. While (!Working-Set empty()) do

9. ia register-interval from Working-Set

10. iiI,next_level_register-interval

11. ii.register_listi.register_list

12. While ( register-interval h for which h.next_level_register-

interval==Unknown & all of h predecessors belong to i &

union (register_list of all h predecessors).size()N) do //N is

maximum number of registers allowed in the register interval

13. if ((union (ii.register_list & h.register_list)N)

(reproduction(N,h)==true)) then

14. h.next_level_register-intervalii

15. ii.register_listunion (ii.register_list & h.register_list)

16. end if

17. end while

18. for each Sinsuccessors() do

19. if (S.next_register-interval==Unknown) then

20. S.next_level_register-intervalnew

next_level_register-interval()

21. Working-Set.insert (S)

22. end if

23. end for

24. end while

شکل 8: مرحله دوم الگوریتم ساخت بازه‌ثبات.

را این گونه تعریف می‌کنیم: قطع‌نشدن بازه زندگی عملوند‌ها از محل تعریف‌شدن ثبات مورد نظر تا آخرین باری که استفاده شده است. بازه زندگی هر ثبات نسبت به بازه‌ثبات‌ جاری در یکی از این دو حالت زیر قرار می‌گیرد:

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

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

شبه‌کد مرحله دوم از الگوریتم ساخت بازه‌ثبات با بازتولید مقادیر میانی در شکل 8 آمده است.

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

شکل 9: نحوه بازتولید مقادیر میانی در صورت تغییر مقادیر اولیه در روش پیشنهادی.

بازه‌ثبات و در نتیجه کاهش احتمال وقفه، بهره می‌برد.

مقادیر مورد نیاز برای بازتولید ممکن است در دسترس نباشند، به این معنی که در طول بازه زندگی مقدار تولیدشده، عملوند‌ها تغییر کرده‌اند. این چالش فرصت بازتولید مقادیر میانی را کاهش می‌دهد. آزمایش‌های ما نشان می‌دهند که این چالش به میزان حدود ۶۰ درصد فرصت بازتولید را از بین می‌برد، به این معنی که در ۶۰ درصد حالت‌ها حداقل یکی از عملوند‌ها تغییر کرده است. برای افزایش فرصت بازتولید، برخی از عملوند‌ها را در حافظه‌‌ای سریع نگهداری می‌کنیم. به این منظور،‌ حافظه‌ای کوچک در کنار حافظه نهان پوشه ثبات اضافه کرده و نام آن را پوشه‌ ثبات عملوند می‌گذاریم. پوشه ثبات عملوند برای هر کلاف فعال در روش LTRF+ چهار ثبات ۱۰۲۴ بیتی در نظر می‌گیرد. این ثبات‌ها به ۴ ثبات انتهایی معماری مجموعه دستورالعمل‌ها تخصیص می‌یابد. نتایج تحلیل‌های ما روی ۳۵ بار کاری نشان می‌دهد که کاهش ۴ ثبات از معماری مجموعه دستورالعمل‌ها تأثیری در کاهش کارایی ندارد چون حداکثر ۱۸۰ ثبات از ۲۵۶ ثبات معماری در بارهای کاری استفاده شده است. روش پیشنهادی، عملوند‌های مورد نیاز را قبل از تغییر به این ثبات‌ها منتقل می‌کند و موقع بازتولید از آن ثبات‌ها می‌خواند. اگر در زمانی که عملوندی در این چهار ثبات قرار دارد،‌ کلاف دچار وقفه طولانی شود به ناچار باید این ثبات‌ها را بازنویسی کرد. برای جلوگیری از این رخداد، این روش تنها برای زمانی استفاده می‌شود که دستورهایی که می‌توانند باعث ایجاد وقفه در اجرای کلاف شوند (مانند دستور‌های حافظه‌ای و پیش‌واکشی ثبات‌ها) در بازه مقداردهی این ثبات‌ها و استفاده از آنها نباشد. لذا در زمان رخداد وقفه طولانی این ثبات‌ها بازنویسی نمی‌شوند. با این روش فرصت بازتولید مقادیر میانی از ۴۰ درصد به ۷۵ درصد می‌رسد. لازم به توضیح است که موقع شمارش ثبات‌ها برای پیش‌واکشی ثبات، ثبات‌های شماره ۲۵۲ تا ۲۵۵ محاسبه نمی‌شوند. شکل 9 با مثالی ساده نحوه بازتولید مقادیر میانی را در صورت تغییر مقادیر اولیه نشان می‌دهد.

شکل 10 به طور خلاصه الگوریتم بازتولید ارائه‌شده را نشان می‌دهد. این الگوریتم بیشینه تعداد مجاز ثبات در بازه‌ثبات و بلوک پایه یا بازه‌ثبات فعلی را به عنوان ورودی می‌گردد و تلاش می‌کند با بازتولید مقادیر میانی، تعداد ثبات‌های آن را کاهش دهد و در نهایت موفقیت و عدم موفقیت را اعلام ‌کند. الگوریتم پیشنهادی، زمان ترجمه را به طور میانگین ۱۰ دقیقه و به طور بیشینه به میزان ۲۵ دقیقه افزایش می‌دهد. البته این هزینه برای هر بار کاری تنها یک بار پرداخت می‌شود. این مقادیر برای روش LTRF به طور میانگین ۲ دقیقه و به طور بیشینه ۷ دقیقه است.

4- متدولوژی ارزیابی

برای ارزیابی روش پیشنهادی از شبیه‌ساز GPGPU-Sim [21] استفاده شده که شبیه‌سازی با یک تناوب دقت است و با تمرکز بر بارهای کاری عام‌منظوره طراحی گردیده است. نحوه ارزیابی به این صورت بوده که 35 بار کاری متعلق به مجموعه برنامه‌های محک CUDA SDK، Rodinia [22] و Parboil [23] را به دو دسته حساس به ثبات و غیر حساس به ثبات دسته‌بندی کردیم. در بارهای کاری حساس به ثبات، پوشه ثبات عامل محدودکننده موازات سطح نخ است. سپس به صورت تصادفی 9 بار کاری از دسته حساس به ثبات و 5 بار کاری از دسته غیر حساس به ثبات انتخاب کرده‌ایم. در ادامه کارایی روش پیشنهادی را
در مقایسه با روش LTRF، پوشه ثبات دوسطحی و معماری پایه پردازنده‌‌های گرافیکی می‌سنجیم.

5- سربار روش پیشنهادی

از آنجایی که روش پیشنهادی این پژوهش، تعداد دستورالعمل‌های اجراشده را افزایش می‌دهد، در این قسمت سربار کارایی و انرژی روش پیشنهادی را می‌سنجیم. سربار کارایی در روش پیشنهادی به دو دلیل محتمل است: 1) به دلیل افزایش تعداد دستورالعمل‌ها، نرخ فقدان حافظه نهان دستور‌العمل افزایش می‌یابد و ۲) افزایش تعداد دستورالعمل‌ها می‌تواند منجر به افزایش زمان اجرای بارهای کاری گردد. معیار سنجش کارایی، زمان اجرای برنامه‌های کاربردی است، زیرا معیار IPC به دلیل تغییر تعداد دستورالعمل‌ها نمی‌تواند به درستی نشانگر میزان سربار روش پیشنهادی باشد.

شکل 11 زمان اجرای بارهای گوناگون کاری برای دو طراحی LTRF با و بدون بازتولید مقادیر میانی را مقایسه می‌کند. در این تحلیل از مزایای بازتولید مقادیر میانی در افزایش تحمل‌پذیری تأخیر صرف نظر شده است. معماری پایه بدون جایگزینی پوشه ثبات بزرگ‌تر و کندتر با همان اندازه 256 کیلوبایت در نظر گرفته شده و تأثیر سربار کارایی مستقل از تحمل‌پذیری تأخیر گزارش شده و نتایج به زمان اجرای بارهای کاری در معماری پایه پردازنده‌های گرافیکی هنجارسازی شده است. توجه شود که در این آزمایش تأخیر دسترسی به پوشه ثبات اصلی در هر دو طراحی، برابر با تأخیر پوشه ثبات در معماری پایه است. مشاهده می‌شود که روش پیشنهادی زمان اجرای بارهای کاری را برای معماری LTRF به میزان 5/0 درصد افزایش می‌دهد که قابل چشم‌پوشی است.

شکل 12 انرژی مصرفی دو طراحی LTRF با و بدون بازتولید مقادیر میانی را مقایسه می‌کند. نتایج به انرژی مصرفی معماری پایه پردازنده گرافیکی هنجارسازی شده است. هر دو طراحی LTRF انرژی مصرفی را کاهش می‌دهد که دلیل آن کاهش توان مصرفی پوشه ثبات است. اما بهبود انرژی در روش LTRF با بازتولید مقادیر میانی (روش پیشنهادی) به میزان 3/4 درصد بیشتر از بهبود انرژی مصرفی در روش LTRF پایه است. این بهبود بیشتر به دلیل کاهش تعداد پیش‌واکشی ثبات و کاهش دسترسی‌ها به پوشه ثبات اصلی رخ می‌‌دهد.

6- تحمل‌پذیری تأخیر دسترسی به پوشه‌ ثبات اصلی

برای مقایسه قدرت تحمل‌کردن تأخیر دسترسی به پوشه ثبات اصلی در طراحی‌های گوناگون، از سنجه معرفی‌شده در مقاله [18] LTRF به نام بیشینه تأخیر قابل تحمل دسترسی به پوشه ثبات اصلی استفاده می‌کنیم. این سنجه در واقع بیان‌کننده تأخیر نسبی، در مقایسه با تأخیر

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

راحیل براتی (نویسنده مسئول)، دانشكده مهندسي كامپيوتر، دانشگاه صنعتی شریف، تهران، ايران، (email: rahil.barati@ipm.ir).

محمد صدرالساداتی، پژوهشگاه دانش‌های بنیادی، تهران، ايران،
(email: sadrosadati@ipm.ir).

حمید سربازی آزاد، دانشكده مهندسي كامپيوتر، دانشگاه صنعتی شریف تهران، ايران، (email: azad@sharif.edu).

[2] . Instruction Level Parallelism

[3] . Graphics Processing Unit

[4] . Pixel

[5] . Operand Collector

[6] . منظور از LTRF در این مقاله، نسخه نهایی ارائه‌شده در [18] است که در آنجا به آن به عنوان LTRF+ اشاره شده است.

[7] . Crossbar

[8] . Backward Branches

شکل 10: مكانيزم پيشنهادي براي بازتوليد مقادير.

شکل 11: تحلیل سربار كارايي روش پیشنهادی بدون افزایش ظرفیت پوشه ثبات.

شکل 12: تحلیل انرژی مصرفی روش پیشنهادی بدون افزایش ظرفیت پوشه‌ ثبات.

شکل 13: تأخير قابل تحمل دسترسي به پوشه ثبات با روش پیشنهادی.

دسترسی پایه پوشه ثبات است که حداکثر 5% کارایی را کاهش می‌دهد. شکل ۱3 نتایج این سنجه را برای چهار طراحی زیر مقایسه می‌کند:

• طراحی BL: این طراحی پایه پردازنده‌های گرافیکی است که در جدول 1 مشخصات آن گزارش شده است. تحمل‌پذیری تأخیر دسترسی به پوشه ثبات در این طراحی، تنها از طریق موازات سطح ریسمان تا حدودی ممکن می‌گردد.

• طراحی ¹RFC: این طراحی از پوشه ثبات دوسطحی بهره می‌برد که قابلیت آن را در تحمل‌کردن تأخیر دسترسی به پوشه ثبات

(الف)

(ب)

شکل 14: تأثير تعداد ثبات‌هاي مجاز در بازه‌ثبات بر اثربخشي روش LTRF، (الف) بدون بازتولید مقادیر میانی و (ب) با بازتولید مقادیر میانی.

(الف)

(ب)

شکل 15: تأثیر تعداد کلاف‌های فعال روی اثربخشی روش LTRF، (الف) بدون بازتولید مقادیر میانی و (ب) با بازتولید مقادیر میانی.

[1] . Register File Caching

جدول 1: فراسنج‌های شبیه‌سازی پردازنده گرافیکی.

تعداد چند پردازنده جریانی	24
فرکانس سیکل ساعت	1137 مگاهرتز
زمان‌بند کلاف	دوسطحی [25]
تعداد کلاف‌ها در هر چند پردازنده جریانی	24
ظرفیت پوشه ثبات در هر چند پردازنده جریانی	256 کیلوبایت (65536 ثبات)
ظرفیت حافظه نهان پوشه ثبات در هر چند پردازنده جریانی	16 کیلوبایت (4096 ثبات)
ظرفیت حافظه مشترک در هر چند پردازنده جریانی	64 کیلوبایت
ظرفیت حافظه نهان سطح اول در هر چند پردازنده جریانی	16 کیلوبایت
ظرفیت حافظه نهان سطح دوم	2 مگابایت
تعداد کلاف‌های فعال در هر چند پردازنده جریانی	8
بیشینه مجاز تعداد ثبات در هر بازه‌ثبات	16

افزایش می‌دهد.

• طراحی LTRF: که معماری پیشنهادی ما برای بهبود آن ارائه شده است.

• طراحی : در این طراحی روش LTRF روی معماری پایه‌ای پیاده‌سازی شده که از بازتولید مقادیر میانی بهره می‌برد.

با بررسی نتایج این آزمایش مشاهده می‌شود که مقدار سنجه بیشینه تأخیر قابل تحمل دسترسی به پوشه ثبات اصلی برای روش LTRF به کمک بازتولید مقادیر میانی به میزان حدود 29 درصد بهبود می‌یابد. این بهبود به دلیل کاهش تعداد بازه‌ثبات‌ها رخ می‌دهد. سپس حساسیت روش پیشنهادی به ظرفیت حافظه نهان پوشه ثبات، مورد بررسی قرار گرفت. به این منظور، ارزیابی قدرت تحمل‌پذیری تأخیر برای روش‌های LTRF با و بدون استفاده از بازتولید مقادیر میانی برای تعداد متفاوت بیشینه ثبات مجاز در بازه‌ثبات و تعداد گوناگون کلاف‌های فعال تکرار شده است.

نمودارهای الف و ب در شکل‌ ۱4 به ترتیب تأثیر تغییر تعداد ثبات‌های مجاز در بازه‌ثبات را برای روش LTRF بدون/ با بازتولید مقادیر میانی نشان می‌دهند. نتایج به معماری پایه پردازنده گرافیکی هنجار شده‌اند. تعداد ثبات‌های مجاز در هر بازه‌ثبات، از 8 تا 32 افزایش داده شده است. مشاهده می‌شود که کارایی روش LTRF با استفاده از بازتولید مقادیر و تعداد 8 ثبات، مشابه کارایی روش LTRF بدون استفاده از بازتولید مقادیر و تعداد 16 ثبات است. به این معنی که با کمک روش LTRF و بازتولید مقادیر می‌توان ظرفیت حافظه نهان را نصف کرد و کارایی همان روش LTRF پایه را به دست آورد.

نمودارهای الف و ب در شکل 15 به ترتیب تأثیر تغییر تعداد کلاف‌های فعال را برای روش LTRF بدون و با استفاده از مکانیزم بازتولید مقادیر نشان می‌دهند. نتایج به معماری پایه پردازنده گرافیکی هنجار شده‌اند
و تعداد کلاف‌های فعال در این آزمایش از 4 تا 16 افزایش یافته است. همان طور که مشاهده می‌شود روش LTRF با استفاده از بازتولید مقادیر میانی و 4 کلاف فعال، نتایج مشابهی با روش LTRF و 8 کلاف فعال می‌دهد. در نتیجه به کمک بازتولید مقادیر می‌توان تعداد کلاف‌های فعال و به تبع آن ظرفیت حافظه نهان پوشه ثبات را نصف کرد.

(الف)

(ب)

شکل 16: كارايي روش LTRF، (الف) بدون بازتولید مقادیر میانی و (ب) با بازتولید مقادیر میانی براي پيكربندي‌هاي گوناگون.

7- افزایش ظرفیت پوشه ثبات با توجه
به بهبود تحمل‌پذیری تأخیر آن

در این بخش از امکاناتی که روش پیشنهادی در اختیار طراحان پردازنده گرافیکی می‌گذارد استفاده می‌کنیم تا کارایی و انرژی پردازنده گرافیکی را بهبود دهیم. در قدم اول از حافظه ¹DWM برای ساخت پوشه ثبات اصلی استفاده می‌کنیم. سلول‌های DWM دارای مصرف توان پایین، خاصیت غیر فراری و تأخیر دسترسی قابل مقایسه با SRAM هستند [24] و بنابراین استفاده از آن در سامانه‌های گوناگون، حافظه روی تراشه و ثانویه صورت گرفته است.

چگالی بالا و مصرف توان پایین سلول حافظه DWM به ما امکان افزایش ظرفیت پوشه ثبات اصلی را با مصرف توان و مساحت روی تراشه قابل قبول می‌دهد، اما در عوض، تأخیر دسترسی به پوشه ثبات اصلی را در حدود ۶ برابر افزایش می‌دهد. هر سلول حافظه DWM قابلیت ذخیره‌سازی یک ثبات ۳۲ بیتی را دارد. با بررسی ۳۵ برنامه پردازنده گرافیکی مشاهده می‌شود که ظرفیت پوشه ثبات اصلی باید حداکثر ۱۵۳۶ کیلو‌بایت باشد. بر این اساس به کمک سلول حافظه DWM ظرفیت پوشه ثبات اصلی را ۶ برابر افزایش می‌دهیم. حال باید تأخیر دسترسی به پوشه ثبات اصلی را به کمک روش پیشنهادی (LTRF بهبودیافته به کمک بازتولید مقادیر میانی) تحمل کنیم. در این مسیر کمترین میزان ظرفیت حافظه نهان پوشه ثبات را از طریق تنظیم فراسنج‌های روش LTRF تعداد کلاف‌های فعال و تعداد ثبات‌ها در بازه‌ثبات، به دست می‌آوریم با این قید که میزان افت کارایی برای بارهای کاری که افزایش ظرفیت پوشه ثبات، کمکی به بهبود موازات سطح نخ نمی‌کند حداکثر ۵ درصد باشد.

7-1 تحلیل کارایی

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

مشاهده می‌شود که اگر از روش بازتولید مقادیر میانی در کنار روش LTRF بهره ببریم، پیکربندی ۴ کلاف فعال و حداکثر ۱۲ ثبات در هر بازه‌ثبات برای تحمل‌کردن تأخیر دسترسی به پوشه ثبات اصلی ساخته‌شده با سلول حافظه DWM کافی است.

بنابراین ظرفیت حافظه نهان پوشه ثبات مورد نیاز ۶ کیلوبایت و ظرفیت پوشه ثبات عملوند ۲ کیلو‌بایت خواهد بود. همچنین مساحت روی تراشه پوشه ثبات ارائه‌شده (به همراه حافظه نهان پوشه ثبات، پوشه ثبات عملوند و سایر مدارهای جانبی روش LTRF) در حدود ۷۰ درصد کمتر از مساحت روی تراشه پوشه ثبات معماری پایه‌ است. با استفاده از ابزار GPUWattch مشاهده می‌شود که فضایی در حدود ۷ میلی‌متر مربع در هر چند پردازنده جریانی آزاد می‌شود که با استفاده از آن می‌توانیم ظرفیت حافظه یکپارچه اختصاص‌یافته به حافظه نهان سطح اول و حافظه مشترک را از ۶۴ کیلوبایت به ۱۲۸ کیلوبایت برسانیم. مطابق شکل 17 در نتیجه به کارگیری پوشه ثبات ۶ برابر بزرگ‌تر و با حافظه نهان سطح اول و مشترک دو برابر بزرگ‌تر، کارایی معماری پیشنهادی نسبت به معماری LTRF با پوشه ثبات 6 برابر بزرگ‌تر تا 86 درصد (به طور میانگین در حدود ۱۸ درصد) بهبود می‌یابد. این بهبود کارایی نسبت به معماری پایه حدود 30 درصد می‌باشد.

شکل 17: نتيجه افزايش دوبرابري حافظه نهان سطح اول و حافظه مشترك در بهبود كارايي.

شکل 18: نتايج توان مصرفي پردازنده گرافيكي با به كارگيري معماري LTRF و بازتوليد مقادير.

7-2 انرژی و توان مصرفی

توان مصرفی پردازنده گرافیکی با به کارگیری معماری پیشنهادی (LTRF و بازتولید مقادیر میانی) برای بارهای کاری گوناگون اندازه‌گیری شد. شکل 18 نتایج هنجارشده مصرف توان برای بارهای کاری گوناگون را نسبت به معماری پایه پردازنده گرافیکی نشان می‌دهد. ابتدا مشاهده می‌شود که معماری پردازنده گرافیکی با پوشه ثبات ۶ برابر بزرگ‌تر به طور میانگین ۸ درصد توان مصرفی پردازنده گرافیکی را کاهش داده است. این بهبود ناشی از به کارگیری معماری LTRF و کاهش دسترسی‌ها
به پوشه ثبات اصلی و سلول‌های DWM است. توجه کنید که بهبود
۸ درصدی با در نظر گرفتن تمام سربار‌های روش پیشنهادی (LTRF و بازتولید مقادیر میانی و اجرای دستور‌العمل‌های بیشتر) به دست آمده است. در ادامه با افزایش دوبرابری ظرفیت حافظه نهان سطح اول و حافظه مشترک، علی‌رغم این که توان مصرفی این حافظه حدود دو برابر افزایش می‌یابد، به دلیل بهبود نرخ برخورد در حافظه نهان، توان شبکه روی تراشه، حافظه نهان سطح دوم و حافظه برون تراشه کاهش می‌یابد که این مهم منجر به بهبود توان مصرفی با میانگین ۱۵ درصد می‌شود.

شکل 19 نتایج هنجارشده مصرف انرژی روش پیشنهادی را نسبت به معماری پایه پردازنده گرافیکی گزارش می‌کند. همان طور که مشاهده می‌شود انرژی پردازنده گرافیکی در حدود ۳8 درصد بهبود می‌یابد.

8- نتیجه‌گیری

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

شکل 19: نتايج انرژي مصرفي پردازنده گرافيكي با معماري LTRF و بازتوليد مقدار میانی.

است. از طرفی افزایش تعداد ثبات‌ قابل استفاده در بازه‌ثبات منجر به افزایش ترافیک پیش‌واکشی و ظرفیت حافظه نهان می‌گردد که راه حل مناسبی برای کاهش تعداد بازه‌ثبات‌ها نیست.

در این پژوهش به کمک بازتولید مقادیر میانی در زمان ترجمه کد، تعداد ثبات‌های مورد نیاز در هر بازه‌ثبات را کاهش دادیم. بنابراین بدون ایجاد تغییر در تعداد مجاز ثبات‌ها می‌توان بازه‌ثبات‌های بزرگ‌تری داشت. نتایج شبیه‌سازی ما نشان داد که روش ما تحمل‌پذیری تأخیر پوشه ثبات در LTRF را به میزان 29 درصد افزایش می‌دهد.

در ادامه، روش پیشنهادی برای طراحی یک پوشه ثبات بزرگ‌تر با
به کارگیری حافظه DWM به کار گرفته شد. نتایج شبیه‌سازی نشان داد که کارایی پردازنده‌ گرافیکی در حالت میانگین به میزان 18 درصد افزایش و انرژی و توان مصرفی به میزان 38 و 15 درصد کاهش یافته است.

مراجع

[1] A. Sethia and S. Mahlke, "Equalizer: dynamic tuning of gpu resources for efficient execution," in Proc. of the IEEE/ACM 47th Annual Int. Symp. on Microarchitecture, pp. 647-658, Cambridge, UK, 13-17 Dec. 2014.

[2] T. D. Han and T. S. Abdelrahman, "hiCUDA: high-level GPGPU programming," IEEE Trans. on Parallel and Distributed Systems, vol. 22, no. 1, pp. 78-90, Jan. 2011.

[3] NVIDIA Corporation. CUDA Programming Guide, V4.0.

[4] NVIDIA Corporation. CUDA Toolkit, 2012. Version 4.2, http://developer.nvidia.com/cuda/cuda-downloads. Sep. 2012.

[5] J. Lee, N. Lakshminarayana, H. Kim, and R. Vuduc, "Many-thread aware prefetching mechanisms for GPGPU applications," in Proc. IEEE/ACM of the 43th Annual Int. Symp. on Microarchitecture, pp. 213-224, Atlanta, GA, USA, 4-8 Dec. 2010.

[6] A. Jog, O. Kayiran, A. Mishra, M. T. Kandemir, O. Mutlu, R. Iyer, and C. R. Das, "Orchestrated scheduling and prefetching for GPGPUs," ACM SIGARCH Computer Architecture News, vol. 41, no. 3, pp. 332-343, Jun. 2013.

[7] A. Jog, O. Kayiran, N. Chidambaram, A. Mishra, M. T. Kandemir, O. Mutlu, R. Iyer, and C. R. Das, "OWL: cooperative thread array aware scheduling techniques for improving GPGPU performance," ACM SIGARCH Computer Architecture News, vol. 41, no. 1, pp. 395-406, Mar. 2013.

[8] A. Sethia, G. Dasika, M. Samadi, and S. Mahlke, "APOGEE: adaptive prefetching on GPUs for energy efficiency," in Proc. of the IEEE 22nd Int. Conf. on Parallel Architectures and Compilation Techniques, pp. 73-82, Edinburgh, UK, 7-11 Sept. 2013.

[9] H. Jeon, G. S. Ravi, N. S. Kim, and M. Annavaram, "GPU register file virtualization," in Proc. IEEE/ACM of the 48th Annual Int. Symp. on Microarchitecture, pp. 420-432, Waikiki, HI, USA, 5-9 Dec. 2015.

[10] M. Abdel-Majeed and M. Annavaram, "Warped register file: a power efficient register file for GPGPUs," in Proc. IEEE 19th Int. Symp. on High Performance Computer Architecture, pp. 412-423, Shenzhen, China, 23-27, Feb. 2013.

[11] S. Lee, K. Kim, G. Koo, H. Jeon, W. W. Ro, and M. Annavaram, "Warped-compression: enabling power efficient GPUs through register compression," ACM SIGARCH Computer Architecture News, vol. 43, no. 3, pp. 502-514, Jun. 2015.

[12] C. Hsiao, S. Chu, and C. Hsieh, "An adaptive thread scheduling mechanism with low-power register file for mobile GPUs," IEEE Trans. on Multimedia, vol. 16, no. 1, pp. 60-67, Sept. 2014.

[13] N. Jing, J. Wang, F. Fan, W. Yu, L. Jiang, C. Li, and X. Liang, "Cache-emulated registerfile: an integrated on-chip memory architecture for high performance gpgpus," in Proc. IEEE/ACM of the 49th Annual Int. Symp. on Microarchitecture, 12 pp., Taipei, Taiwan, 10-15?, Oct. 2016.

[14] H. Asghari Esfeden, A. A. Abdolrashidi, S. Rahman, D. Wong, and N. Abu-Ghazaleh, "BOW: breathing operand windows to exploit bypassing in GPUs," in Proc. IEEE/ACM of the 53th Annual Int. Symp. on Microarchitecture, pp. 996-1008, Athens, Greece, 17-21 Oct. 2020.

[15] F. Khorasani, H. A. Esfeden, A. Farmahini-Farahani, N. Jayasena, and V. Sarkar, "Regmutex: inter-warp gpu register time-sharing," in Proc. of the 45th Annual Int. Symp. on Computer Architecture, pp. 816-828, Providence, RI, USA, 13-17 Apr. 2018.

[16] H. Asghari Esfeden, F. Khorasani, H. Jeon, D. Wong, and N.
Abu-Ghazaleh, "CORF: coalescing operand register file for GPUs," in Proc. of the 24th Int. Conf. on Architectural Support for Programming Languages and Operating Systems, pp. 701-714, Boston, MA, USA, 14-17 Oct. 2019.

[17] J. Kloosterman, et al., "Regless: just-in-time operand staging for gpus," in Proc. IEEE/ACM of the 50th Annual Int. Symp. on Microarchitecture, pp. 151-164, Boston, MA, USA, 14-17, Oct. 2017.

[18] M. Sadrosadati, A. Mirhosseini, S. B. Ehsani, H. Sarbazi-Azad, M. Drumond, B. Falsafi, R. Ausavarungnirun, and O. Mutlu, "Ltrf: enabling high-capacity register files for gpus via hardware/software cooperative register prefetching," in Proc. of the 23rd Int. Conf. on Architectural Support for Programming Languages and Operating Systems, pp. 489-502, Williamsburg, VA, USA, 24-18 Mar. 2018.

[19] J. E. Lindholm, M. Y. Siu, S. S. Moy, S. Liu, and J. R. Nickolls, Simulating Multiported Memories Using Lower Port Count Memories, US Patent 7,339,592, 2008.

[20] LTRF Register-Interval-Algorithm, https://github.com/CMU-SAFARI/Register-Interval, 2018.

[21] A. Bakhoda, G. L. Yuan, W. W. Fung, H. Wong, and T. M. Aamodt, "Analyzing cuda workloads using a detailed gpu simulator," ISPASS. in Proc. IEEE Int. Symp. on Performance Analysis of Systems and Software,, pp. 163-174, Boston, MA, USA, 26-28 Apr. 2009.

[22] S. Che, et al., "Rodinia: a benchmark suite for heterogeneous computing," in Proc. IEEE Int. Symp. on Workload Characterization, pp. 44-54, Austin, TX, USA, 4-6 Oct. 2009.

[23] J. A. Stratton, et al., "Parboil: a revised benchmark suite for scientific and commercial throughput computing," Center for Reliable and High-Performance Computing, vol. 127, p. 27, Mar. 2012.

[24] R. Venkatesan, S. G. Ramasubramanian, S. Venkataramani, K.
Roy, and A. Raghunathan, "Stag: spintronic-tape architecture for GPGPU cache hierarchies," in Proc. IEEE Int. Symp. on Computer Architecture, pp. 253-264, Minneapolis, MN, USA, 14-18 Jun. 2014.

[25] V. Narasiman, M. Shebanow, C. J. Lee, R. Miftakhutdinov, O. Mutlu, and Y. N. Patt, "Improving gpu performance via large warps and two-level warp scheduling," in Proc. IEEE/ACM of the 44th Annual Int. Symp. on Microarchitecture, pp. 308-317, Porto Alegre, Brazil, 3-7, Dec. 2011.

راحیل براتی در حال حاضر به عنوان دستیار پژوهشی در پژوهشگاه دانش‌های بنیادی فعالیت می‌کند. او مدرک کارشناسی و کارشناسی ارشد خود را به ترتیب در سال‌های 1395 و 1398 از دانشگاه صنعتی شریف اخذ نموده است. موضوعات مرتبط با سیستم‌های چندهسته‌ای، پردازنده‌های گرافیگی و سیستم‌های حافظه از زمینه‌های تحقیقاتی مورد علاقه او است.

سید محمد صدرالساداتی در حال حاضر پژوهشگر پسادكترا در پژوهشگاه دانش‌های بنیادی است. او مدرک کارشناسی، کارشناسی ارشد و دکترای خود را در رشته‌ی مهندسی کامپیوتر به ترتیب در سال‌های 1391، 1393 و 1398 از دانشگاه صنعتی شریف کسب کرد. از حوزه‌های تحقیقاتی مورد علاقه وی می‌توان به معماری سیستم‌های چندهسته‌ای و زیادهسته‌ای، سیستم‌های حافظه و پردازش داخل حافظه اشاره کرد. وی در حوزه‌های تحقیقاتی خود مقالات متنوعی در همایش‌ها و ژورنال‌های معتبر بین‌المللی به چاپ رسانده است. در نتیجه تحقیقات عمیق وی در بهبود کارآمدی مصرف انرژی در پردازنده‌های گرافیکی، او در سال 1399 به عنوان برگزیده اول جشنواره جوان خوارزمی در بخش پژوهش‌های بنیادی انتخاب شد.

حمید سربازی آزاد مدرک کارشناسی خود را در رشته مهندسی کامپیوتراز دانشگاه شهید بهشتی در سال 1992 اخذ نمود، وی مدرک کارشناسی ارشد و دکتری خود را در رشته مهندسی کامپیوتر به ترتیب در سال‌های 1994 و 2002 از دانشگاه‌های صنعتی شریف و گلاسکو انگلستان کسب کرد. او هم‌اکنون استاد تمام دانشگاه صنعتی شریف و استاد پژوهشگر در پژوهشگاه دانش‌های بنیادی است. از علایق پژوهشی وی می‌توان به معماری کامپیوتر، معماری حافظه، شبکه و سیستم‌های روی تراشه، سیستم‌های موازی و توزیع شده، مدلسازی و ارزیابی کارایی و سیستم‌های ذخیره‌سازی اشاره کرد. وی دارای بیش از 300 مقاله منتشر شده در کنفرانس‌ها و مجلات معتبر بین‌المللی است. او همچنین، موفق به کسب جایزه بین‌المللی خوارزمی در سال 2006 و جایزه دانشمند جوان TWAS در سال 2007 شده و در سال‌های 2004، 2007، 2008، 2010 و 2013 به عنوان پژوهشگر برتر دانشگاه صنعتی شریف انتخاب شده است..

[1] . Domain Wall Memory

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

Improving Register File Access Latency Tolerance in GPUs by Value Reproduction