检索结果-内蒙古大学图书馆

SAT-based Exact modulo scheduling Mapping for Resource-Constrained CGRAs

ACM JOURNAL ON EMERGING TECHNOLOGIES IN COMPUTING SYSTEMS 2024年第3期20卷 1-26页

作者： Tirelli, Cristian Sapriza, Juan Alvarez, Ruben Podriguez Ferretti, Lorenzo Denkinger, Benoit Ansaloni, Giovanni Calero, Jose Miranda Atienza, David Pozzi, Laura Univ Svizzera Italiana SYS Inst Lugano Switzerland Ecole Polytech Fed Lausanne Lausanne Switzerland Micron Technol San Jose CA USA Ecole Polytech Fed Lausanne SYS Inst Lausanne Switzerland

Coarse-Grain Reconfigurable Arrays (CGRAs) represent emerging low-power architectures designed to accelerate Compute-Intensive Loops (CILs). The effectiveness of CGRAs in providing acceleration relies on the quality of mapping: how efficiently the CIL is compiled onto the platform. State-of-the-Art (SoA) compilation techniques utilize modulo scheduling to minimize the Iteration Interval (II) and use graph algorithms like Max-Clique Enumeration to address mapping challenges. Our work approaches the mapping problem through a satisfiability (SAT) formulation. We introduce the Kernel Mobility Schedule (KMS), an ad hoc schedule used with the Data Flow Graph and CGRA architectural information to generate Boolean statements that, when satisfied, yield a valid mapping. Experimental results demonstrate SAT-MapIt outperforming SoA alternatives in almost 50% of explored benchmarks. Additionally, we evaluated the mapping results in a synthesizable CGRA design and emphasized the runtime metrics trends, i.e., energy efficiency and latency, across different CILs and CGRA sizes. We show that a hardware-agnostic analysis performed on compiler-level metrics can optimally prune the architectural design space, while still retaining Pareto-optimal configurations. Moreover, by exploring how implementation details impact cost and performance on real hardware, we highlight the importance of holistic software-to-hardware mapping flows, as the one presented herein.

关键词： Coarse-grained reconfigurable arrays hardware acceleration modulo scheduling

来源：评论

学校读者我要写书评

暂无评论

Efficient Operator Sharing modulo scheduling for Sum-Product Network Inference on FPGAs 21st

Efficient Operator Sharing Modulo Scheduling for Sum-Product...

引用

21st International Conference on Embedded Computer Systems - Architectures, Modeling, and Simulation (SAMOS)

作者： Kruppe, Hanna Sommer, Lukas Weber, Lukas Oppermann, Julian Axenie, Cristian Koch, Andreas Tech Univ Darmstadt Embedded Syst & Applicat Grp Darmstadt Germany Huawei Munich Res Ctr Intelligent Cloud Technol Lab Munich Germany

ISBN: (纸本)9783031045806;9783031045790

Probabilistic models are receiving increasing attention as a complementary alternative to more widespread machine learning approaches such as neural networks. One particularly interesting class of models, so-called Sum-Product Networks (SPNs), combine the expressiveness of probabilistic models with tractable inference, making them an interesting candidate for use in real-world applications. Previously, inference in SPNs has successfully been accelerated by fully pipelined FPGA-based hardware. However, with these approaches, the maximum size of the SPN for FPGA acceleration has effectively been limited by the fully spatial mapping of arithmetic operations into hardware and the number of available resources in the FPGA. In this work, we present an extended and specialized modulo scheduling algorithm based on Integer Linear Programming (ILP) for time-multiplexed sharing of hardware arithmetic operators in the SPN inference accelerator. In addition and in order to scale the scheduling to large SPN graphs, we combine the scheduling algorithm with a graph-partitioning heuristic, exploiting the graph structure of SPNs. The combination of heuristic graph partitioning and ILP-based scheduling allows generating pipe-lined accelerators with the best possible initiation interval, while limiting the resource utilization to pre-set bounds. The evaluation discusses the effect different parameters have on convergence time and solution quality. A performance comparison shows that the FPGA improves the inference throughput over a comparable CPU- and GPU platform by a factor (geo.-mean) of 4.4x and 1.7x, respectively.

关键词： FPGA Machine learning Probabilistic model Sum-product network modulo scheduling Graph partitioning

来源：评论

学校读者我要写书评

暂无评论

Evaluating a Dynamic and a modulo scheduling-based Static Approach for Configuration Generation in CGRA Accelerators

引用

IEEE LATIN AMERICA TRANSACTIONS 2020年第12期18卷 2166-2173页

作者： Ribeiro, Lucas Fernandes Silva Junior, Francisco Carlos Silva, Ivan Saraiva Univ Brasilia Brasilia DF Brazil Univ Fed Piaui Teresina Brazil

With the increasing complexity of the applications, there is an urgent need for solutions to improve the performance of these applications. It is noted that the loops present in some of them are responsible for up to 71% of the code execution time. So, optimizing the loop's execution it is possible to accelerate the execution of the whole application. This performance gain can be obtained with the use of software pipelining. This work proposes RENOIR, a tool that uses software pipelining technique through the implementation of the modulo scheduling algorithm, developed in software, that acts in the generation of configurations for a coarse-grained reconfigurable architecture (CGRA). RENOIR is implemented in a compiler, which receives an application and generates a code that can run on a gem5 implementation of a CGRA that includes a RISC-V microprocessor and a thin reconfigurable array. The results show that all the applications tested achieved an improvement in performance, reaching a gain of 2,32x in certain applications.

关键词： Hardware Kernel Software Pipeline processing Computer architecture VLIW Tools modulo scheduling Reconfigureable Architectures Software pipelining

来源：评论

学校读者我要写书评

暂无评论

Towards Higher Performance and Robust Compilation for CGRA modulo scheduling

引用

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS 2020年第9期31卷 2201-2219页

作者： Zhao, Zhongyuan Sheng, Weiguang Wang, Qin Yin, Wenzhi Ye, Pengfei Li, Jinchao Mao, Zhigang Shanghai Jiao Tong Univ Dept Micro Nano Elect Shanghai 200240 Peoples R China Nvidia Shanghai Peoples R China

Coarse-Grained Reconfigurable Architectures (CGRA) is a promising solution for accelerating computation intensive tasks due to its good trade-off in energy efficiency and flexibility. One of the challenging research topic is how to effectively deploy loops onto CGRAs within acceptable compilation time. modulo scheduling (MS) has shown to be efficient on deploying loops onto CGRAs. Existing CGRA MS algorithms still suffer from the challenge of mapping loop with higher performance under acceptable compilation time, especially mapping large and irregular loops onto CGRAs with limited computational and routing resources. This is mainly due to the under utilization of the available buffer resources on CGRA, unawareness of critical mapping constraints and time consuming method of solving temporal and spatial mapping. This article focus on improving the performance and compilation robustness of the modulo scheduling mapping algorithm for CGRAs. We decomposes the CGRA MS problem into the temporal and spatial mapping problem and reorganize the processes inside these two problems. For the temporal mapping problem, we provide a comprehensive and systematic mapping flow that includes a powerful buffer allocation algorithm, and efficient interconnection & computational constraints solving algorithms. For the spatial mapping problem, we develop a fast and stable spatial mapping algorithm with backtracking and reordering mechanism. Our MS mapping algorithm is able to map loops onto CGRA with higher performance and faster compilation time. Experiment results show that given the same compilation time budget, our mapping algorithm generates higher compilation success rate. Among the successfully compiled loops, our approach can improve 5.4 to 14.2 percent performance and takes x24 to x1099 less compilation time in average comparing with state-of-the-art CGRA mapping algorithms.

关键词： Routing Registers Signal processing algorithms System-on-chip Robustness Processor scheduling Computer architecture CGRA modulo scheduling temporal mapping spatial mapping

来源：评论

学校读者我要写书评

暂无评论

CRIMSON: Compute-Intensive Loop Acceleration by Randomized Iterative modulo scheduling and Optimized Mapping on CGRAs

引用

IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS 2020年第11期39卷 3300-3310页

作者： Balasubramanian, Mahesh Shrivastava, Aviral Arizona State Univ Sch Comp Informat Decis & Syst Engn Tempe AZ 85287 USA Arizona State Univ Sch Comp Informat Decis & Syst Engn Tempe AZ 85048 USA

Coarse-grain reconfigurable arrays (CGRAs) are emerging accelerators that promise low-power acceleration of compute-intensive loops in applications. The acceleration achieved by CGRA relies on the efficient mapping of the compute-intensive loops by the CGRA compiler, onto the CGRA architecture. The CGRA mapping problem, being NP-complete, is performed in a two-step process, namely, scheduling and mapping. The scheduling algorithm allocates timeslots to the nodes of the data flow graph, and the mapping algorithm maps the scheduled nodes onto the processing elements of the CGRA. On a mapping failure, the initiation interval (II) is increased and a new schedule is obtained for the increased II. Most previous mapping techniques use the iterative modulo scheduling (IMS) algorithm to find a schedule for a given II. Since IMS generates a resource-constrained as-soon-as-possible (ASAP) scheduling, even with increased II, it tends to generate a similar schedule that is not mappable. Therefore, IMS does not explore the schedule space effectively. To address these issues, this article proposes CRIMSON, compute-intensive loop acceleration by randomized IMS and optimized mapping technique that generates random modulo schedules by exploring the schedule space, thereby creating different modulo schedules at a given and increased II. CRIMSON also employs a novel conservative test after scheduling to prune valid schedules that are not mappable. From our study conducted on the top 24 performance-critical loops (run for more than 7% of application time) from MiBench, Rodinia, and Parboil, we found that previous state-of-the-art approaches that use IMS, such as RAMP and GraphMinor could not map five and seven loops, respectively, on a 4 x 4 CGRA, whereas CRIMSON was able to map them all. For loops mapped by the previous approaches, CRIMSON achieved a comparable II.

关键词： Coarse-grained reconfigurable arrays (CGRAs) compiler modulo scheduling randomized scheduling

来源：评论

学校读者我要写书评

暂无评论

SplitMS: Split modulo-scheduling for Accelerating Loops onto CGRAs 27

SplitMS: Split Modulo-Scheduling for Accelerating Loops onto...

引用

27th Euromicro Conference on Digital System Design

作者： Sajan, Christie Sajitha Martin, Kevin J. M. Das, Satyajit Coussy, Philippe Univ Bretagne Sud CNRS UMR 6285 Lab STICC Lorient France IIT Palakkad Kanjikode India

ISBN: (纸本)9798350380392;9798350380385

Coarse-Grained Reconfigurable Array (CGRA) architectures are popular for accelerating loop kernels due to a good balance between energy efficiency and flexibility. modulo scheduling (MS) is the preferred solution for efficiently mapping loops onto CGRAs. Existing CGRA MS algorithms suffer from low resource utilization if the number of operation nodes in the Data Flow Graph (DFG) is less than the number of Processing Elements (PEs) in the CGRA. To improve instruction level parallelism (ILP), the common approaches unroll the loop before applying MS. However, finding valid MS solutions for larger DFGs becomes difficult for CGRAs with resource constraints. This paper proposes a novel Split modulo-scheduling (SplitMS) technique to improve the ILP by segmenting the target CGRA into clusters and mapping loop chunks. We also present a lightweight hardware approach to support the cluster execution. Experiments show that SplitMS for a 4x[2x2] CGRA cluster achieves an average speedup of 2.8x over MS for a 4x4 target CGRA with 8 Load-Store Units (LSUs). SplitMS increases an average of 2.9x the PE utilization and 3x the energy efficiency over the conventional MS approach.

关键词： CGRA Loop Splitting Loop Unrolling modulo scheduling

来源：评论

学校读者我要写书评

暂无评论

Scaling Up modulo scheduling for High-Level Synthesis

引用

IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS 2019年第5期38卷 912-925页

作者： Rosa, Leandro de Souza Bouganis, Christos-Savvas Bonato, Vanderlei Univ Sao Paulo Inst Math & Comp Sci BR-05508900 Sao Carlos SP Brazil Imperial Coll London Dept Elect & Elect Engn London SW7 2AZ England

High-level synthesis (HLS) tools have been increasingly used within the hardware design community to bridge the gap between productivity and the need to design large and complex systems. When targeting heterogeneous systems, where the CPU and the field-programmable gate array (FPGA) fabric are both available to perform computations, a design space exploration (DSE) is usually carried out for deciding which parts of the initial code should be mapped to the FPGA fabric such as the overall system's performance is enhanced by accelerating its computation via dedicated processors. As the targeted systems become more complex and larger, leading to a large DSE, the fast estimative of the possible acceleration that can be obtained by mapping certain functionality into the FPGA fabric is of paramount importance. Loop pipelining, which is responsible for the majority of HLS compilation time, is a key optimization toward achieving high-performance acceleration kernels. A new modulo scheduling algorithm is proposed, which reformulates the classical modulo scheduling problem and leads to a reduced number of integer linear problems solved, resulting in large computational savings. Moreover, the proposed approach has a controlled tradeoff between solution quality and computation time. Results show the scalability is improved efficiently from quadratic, for the state-of-the-art method, to linear, for the proposed approach, while the optimized loop suffers a 1% (geomean) increment in the total number of cycles.

关键词： Genetic algorithm (GA) high-level synthesis (HLS) loop pipeline modulo scheduling

来源：评论

学校读者我要写书评

暂无评论

Exact and Practical modulo scheduling for High-Level Synthesis

引用

ACM TRANSACTIONS ON RECONFIGURABLE TECHNOLOGY AND SYSTEMS 2019年第2期12卷 8-8页

作者： Oppermann, Julian Reuter-Oppermann, Melanie Sommer, Lukas Koch, Andreas Sinnen, Oliver Tech Univ Darmstadt Hochschulstr 10 D-64289 Darmstadt Germany Karlsruhe Inst Technol Kaiserstr 89 D-76131 Karlsruhe Germany Univ Auckland Privale Bag 92019 Auckland 1142 New Zealand

Loop pipelining is an essential technique in high-level synthesis to increase the throughput and resource utilisation of field-programmable gate array-based accelerators. It relies on modulo schedulers to compute an operator schedule that allows subsequent loop iterations to overlap partially when executed while still honouring all precedence and resource constraints. modulo schedulers face a bi-criteria problem: minimise the initiation interval (II;i.e., the number of timesteps after which new iterations are started) and minimise the schedule length. We present Moovac, a novel exact formulation that models all aspects (including the II minimisation) of the modulo scheduling problem as a single integer linear program, and discuss simple measures to prevent excessive runtimes, to challenge the old preconception that exact modulo scheduling is impractical. We substantiate this claim by conducting an experimental study covering 188 loops from two established high-level synthesis benchmark suites, four different time limits, and three bounds for the schedule length, to compare our approach against a highly tuned exact formulation and a state-of-the-art heuristic algorithm. In the fastest configuration, an accumulated runtime of under 16 minutes is spent on scheduling all loops, and proven optimal IIs are found for 179 test instances.

关键词： modulo scheduling exact optimal II minimisation high-level synthesis

来源：评论

学校读者我要写书评

暂无评论

Joint modulo scheduling and Memory Partitioning with Multi-Bank Memory for High-Level Synthesis 17

Joint Modulo Scheduling and Memory Partitioning with Multi-B...

引用

ACM/SIGDA International Symposium on Field-Programmable Gate Arrays

作者： Lu, Tianyi Yin, Shouyi Yao, Xianqing Xie, Zhicong Liu, Leibo Wei, Shaojun Tsinghua Univ Beijing Peoples R China

ISBN: (纸本)9781450343541

High-Level Synthesis (HLS) has been widely recognized and accepted as an efficient compilation process targeting FPGAs for algorithm evaluation and product prototyping. However, the massively parallel memory access demands and the extremely expensive cost of single-bank memory with multi-port have impeded loop pipelining performance. Thus, based on an alternative multi-bank memory architecture, a joint approach that employs memory-aware force directed scheduling and multi-cycle memory partitioning is formally proposed to achieve legitimate pipelining kernel and valid bank mapping with less resource consumption and optimal pipelining performance. The experimental results over a variety of benchmarks show that our approach can achieve the optimal pipelining performance and meanwhile reduce the number of multiple independent memory banks by 55.1% on average, compared with the state-of-the-art approaches.

关键词： modulo scheduling Memory Partitioning Multi-bank HLS

来源：评论

学校读者我要写书评

暂无评论

A Dynamic modulo scheduling with Binary Translation: Loop optimization with software compatibility

引用

JOURNAL OF SIGNAL PROCESSING SYSTEMS FOR SIGNAL IMAGE AND VIDEO TECHNOLOGY 2016年第1期85卷 45-66页

作者： Ferreira, Ricardo Denver, Waldir Pereira, Monica Wong, Stephan Lisboa, Carlos A. Carro, Luigi Univ Fed Vicosa Dept Comp Sci Vicosa MG Brazil Univ Fed Vicosa Vicosa MG Brazil Univ Fed Rio Grande do Norte Natal RN Brazil Delft Univ Technol Delft Netherlands Univ Fed Rio Grande do Sul Porto Alegre RS Brazil

In the past years, many works have demonstrated the applicability of Coarse-Grained Reconfigurable Array (CGRA) accelerators to optimize loops by using software pipelining approaches. They are proven to be effective in reducing the total execution time of multimedia and signal processing applications. However, the run-time reconfigurability of CGRAs is hampered overheads introduced by the needed translation and mapping steps. In this work, we present a novel run-time translation technique for the modulo scheduling approach that can convert binary code on-the-fly to run on a CGRA. We propose a greedy approach, since the modulo scheduling for CGRA is an NP-complete problem. In addition to read-after-write dependencies, the dynamic modulo scheduling faces new challenges, such as register insertion to solve recurrence dependences and to balance the pipelining paths. Our results demonstrate that the greedy run-time algorithm can reach a near-optimal ILP rate, better than an off-line compiler approach for a 16-issue VLIW processor. The proposed mechanism ensures software compatibility as it supports different source ISAs. As proof of concept of scaling, a change in the memory bandwidth has been evaluated. In this analysis it is demonstrated that when changing from one memory access per cycle to two memory accesses per cycle, the modulo scheduling algorithm is able to exploit this increase in memory bandwidth and enhance performance accordingly. Additionally, to measure area and performance, the proposed CGRA was prototyped on an FPGA. The area comparisons show that a crossbar CGRA (with 16 processing elements and including an 4-issue VLIW host processor) is only 1.11 x bigger than a standalone 8-issue VLIW softcore processor.

关键词： modulo scheduling Binary translation Run-time Coarse-grained reconfigurable accelerator

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：