Véra Salvisberg · Infoscience (Ecole Polytechnique Fédérale de Lausanne) · 2014
This is my master thesis done at PPL in Stanford under the supervision of Prof. Kunle Olukotun. It improved LMS, a framework for embedding DSLs (domain-specific languages) into Scala which features many general optimizations that can be used by any DSLs for free. I implemented a more powerful and cleaner version of the loop fusion optimization from the compiler world. Loop fusion is an important performance optimization for all languages that feature list comprehensions and translate their high-level operations into loop-based representations. It can decrease runtime, memory footprint and code size through two different fusion cases: The simpler one is called horizontal or side-by-side fusion and fuses adjacent loops iterating over the same range, enabling further optimizations. The second one is vertical or pipeline fusion, where a producer and a consumer of data are fused, removing the need for the intermediate data structure.
Cited by 0Open access
Qubo Hu, M. Palkovic, Per Gunnar Kjeldsberg · 2004
Loop fusion and loop shifting are well recognized loop transformations for memory requirement reduction. State-of-the-art optimizations with loop fusion and shifting are based on heuristics without any evaluation of the resulting effects during each optimization step. Thus we cannot guarantee that each step results in a reduced overall memory requirement. On the other hand, most memory requirement estimations at system level are inefficient and slow. Also the estimation is not started until the optimization is done. Having to iterate between optimization and estimation is very time consuming. In this paper, we present a storage requirement optimization method which combines the optimization and estimation processes with the goal to have continuous estimates during the optimization and hence to achieve lower memory requirements.
Cited by 1
Gerald Roth, Ken Kennedy · 1998
Article Free Access Share on Loop fusion in high performance Fortran Authors: Gerald Roth Sun Microsystems, 901 San Antonio Rd., MS UMPK16-303 Palo Alto, CA Sun Microsystems, 901 San Antonio Rd., MS UMPK16-303 Palo Alto, CAView Profile , Ken Kennedy Rice University, Computer Science Dept., 6100 Main Street, Houston, TX Rice University, Computer Science Dept., 6100 Main Street, Houston, TXView Profile Authors Info & Claims ICS '98: Proceedings of the 12th international conference on SupercomputingJuly 1998 Pages 125–132https://doi.org/10.1145/277830.277857Published:13 July 1998Publication History 14citation363DownloadsMetricsTotal Citations14Total Downloads363Last 12 Months22Last 6 weeks2 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF
Cited by 22
Madushan Abeysinghe, Jesse Villarreal, Todd T. Hahn et al. · 2024
In this paper, we develop a method for automatically selecting groups of loops to fuse in an image processing data flow graph, here referred to as a "fusing configuration". The method is designed for use on Digital Signal Processors (DSP), many of which rely on statically scheduled Very Long Instruction Word architecture. Selection is guided by a heuristic instruction scheduler that serves as a performance model for a candidate configuration. We show that for synthetically generated graphs of size 2 to 10 nodes, this approach is capable of selecting the optimal fusing configuration in 80% of graphs and selects a configuration that achieves within 10% of the performance of the optimal configuration for 90% of graphs.
Cited by 0Open access
Laboratoire de l'informatique du parallélisme, Darte, Alain · LARA - Libre Acces aux Rapports scientifiques et techniques · 2006
(eng) Loop fusion is a program transformation that combines several loops into one. It is used in parallelizing compilers mainly for increasing the granularity of loops and for improving data reuse. The goal of this report is to study, from a theoretical point of view, several variants of the loop fusion problem -- identifying polynomially solvable cases and NP-complete cases -- and to make the link between these problems and some scheduling problems that arise from completely different areas. We study, among others, the fusion of loops of different types, and the fusion of loops when combined with loop shifting.
Cited by 0
Yi Qian Science, Yi Qian · 2002
Embedded systems require maximum performance from a processor within significant constraints in power consumption and chip cost. Using software pipelining, high-performance digital signal processors can often exploit considerable instruction-level parallelism (ILP), and thus significantly improve performance. However, software pipelining, in some instances, hinders the goals of low power consumption and low chip cost. Specifically, the registers required by a software pipelined loop may exceed the size of the physical register set.
Cited by 0
Alain Darte · HAL (Le Centre pour la Communication Scientifique Directe) · 1998
Loop fusion is a program transformation that combines several loops into one. It is used in parallelizing compilers mainly for increasing the granularity of loops and for improving data reuse. The goal of this paper is to study, from a theoretical point of view, several variants of the loop fusion problem identifying polynomially solvable cases and NP-complete cases and to make the link between these problems and some scheduling problems that arise from completely dierent areas. We study, among others, the fusion of loops of dierent types, and the fusion of loops when combined with loop shifting. Key words: Parallelization, loop fusion, loop distribution, complexity. 1 Introduction Loop fusion is a program transformation that collapses several loops into one. The resulting program compaction and the corresponding increase in the size of the loop body has several well-known impacts on the performances of a program [18]. It was rst used to reduce the cost of loop bound testing....
Cited by 0Open access
Guang R. Gao, Runar Bergheim Olsen, Vivek Sarkar et al. · Lecture notes in computer science · 1993
Cited by 128
Antoine Fraboulet, Karen Kodary, Anne Mignotte · 2001
Portable or embedded systems as well as submicronic technologies have made the power consumption criterium crucial. Memory is known to be extremely power consuming. Moreover multimedia applications are memory intensive applications. Therefore, we propose new techniques to optimize a behavioral description of multimedia applications before the hardware/software partitioning (Codesign). These transformations are performed on "for" loops that constitute the main parts which handle the arrays of the multimedia code. This paper presents an optimal algorithm to reduce the use of temporary arrays by loop fusion. Although the algorithm is not polynomial, experiments have shown that it is very efficient.
Cited by 3
J. Hammes, A.P.W. Böhm · 2001
This paper describes a system for compiling codes written in a conventional high-level language to reconfigurable FPGA-based hardware. SA-C is a single-assignment language, and its compiler performs a variety of optimizations, some conventional and some specialized, before generating dataflow graphs. The dataflow graphs are then compiled to VHDL. Three novel compiler optimizations are described here, all based on loops with windowing behavior. Loop fusion with windows requires a unique approach to producer-consumer fusion. Temportal Common Subexpression Elimination identifies expressions that recompute values that were computed in previous iterations, and replaces them with registers. Window narrowing reduces window sizes after other optimizations have been applied. Finally, the performance effects of these optimizations on a four-loop sequence are shown.
Cited by 0
Robert Szafarczyk, Syed Waqar Nabi, Wim Vanderbauwhede · 2025
Dynamic High-Level Synthesis (HLS) uses additional hardware to perform memory disambiguation at runtime, increasing loop throughput in irregular codes compared to static HLS. However, most irregular codes consist of multiple sibling loops, which currently have to be executed sequentially by all HLS tools. Static HLS performs loop fusion only on regular codes, while dynamic HLS relies on loops with dependencies to run to completion before the next loop starts.
Cited by 1Open access
P. Kristel, Konrad Waldorf · Compositio Mathematica · 2024
The loop space of a string manifold supports an infinite-dimensional Fock space bundle, which is an analog of the spinor bundle on a spin manifold. This spinor bundle on loop space appears in the description of two-dimensional sigma models as the bundle of states over the configuration space of the superstring. We construct a product on this bundle that covers the fusion of loops, i.e. the merging of two loops along a common segment. For this purpose, we exhibit it as a bundle of bimodules over a certain von Neumann algebra bundle, and realize our product fibrewise using the Connes fusion of von Neumann bimodules. Our main technique is to establish novel relations between string structures, loop fusion, and the Connes fusion of Fock spaces. The fusion product on the spinor bundle on loop space was proposed by Stolz and Teichner as part of a programme to explore the relation between generalized cohomology theories, functorial field theories, and index theory. It is related to the pair of pants worldsheet of the superstring, to the extension of the corresponding smooth functorial field theory down to the point, and to a higher-categorical bundle on the underlying string manifold, the stringor bundle.
Cited by 1Open access
Antoine Fraboulet, Karen Kodary, Anne Mignotte · 2008
Portable or embedded systems as well as submicronic technologies have made the power consumption criterium crucial. Memory is known to be extremely power consuming. Moreover multimedia applications are memory intensive applications. Therefore, we propose new techniques to optimize a behavioral description of multimedia applications before the hardware/software partitioning (Codesign). These transformations are performed on “for ” loops that constitute the main parts which handle the arrays of the multimedia code. This paper presents an optimal algorithm to reduce the use of temporary arrays by loop fusion. Although the algorithm is not polynomial, experiments have shown that it is very efficient. 1.
Cited by 0
Liushuai Li (17889588), Tingting Chong (17889591), Lu Peng (769036) et al. · Figshare · 2024
Cited by 0Open access
Peter Kristel, Konrad Waldorf · arXiv (Cornell University) · 2020
The loop space of a string manifold supports an infinite-dimensional Fock space bundle, which is an analog of the spinor bundle on a spin manifold. This spinor bundle on loop space appears in the description of 2-dimensional sigma models as the bundle of states over the configuration space of the superstring. We construct a product on this bundle covering the fusion of loops, i.e., the merging of two loops along a common segment. For this purpose, we exhibit it as a bundle of bimodules over a certain von Neumann algebra bundle, and realize our product fibrewise using the Connes fusion of von Neumann bimodules. Our main technique is to establish a novel relation between string structures, loop fusion, and the Connes fusion of Fock spaces. The fusion product on the spinor bundle on loop space was proposed by Stolz and Teichner as a part of a programme to explore the relation between generalized cohomology theories, functorial field theories, and index theory. It is related to the pair of pants worldsheet of the superstring, to the extension of the corresponding smooth functorial field theory down to the point, and to a higher-categorical bundle on the underlying string manifold, the stringor bundle.
Cited by 0Open access
Sharad Singhai, Kathryn Mckinley · 1996
Modern processors use memory hierarchy of several levels. Achieving high performance mandates the effective use of the cache locality. Compiler transformations can relieve the programmer from handoptimizing for the specific machine architectures. Loop fusion is a reordering transformation that merges multiple loops into a single loop. It can increase data locality thereby exploiting better cache locality; it can also increase the granularity of parallel loops, thereby decreasing barrier synchronization overhead and improving program performance. However, very large granularity loops are undesirable, if they introduce register spills inside the loop. Previous approaches to the fusion problem have considered all these factors in isolation. In this work, we present a new model which considers data locality and parallelism together subject to the register pressure. We build a weighted directed acyclic graph, called the fusion graph, in which the nodes represent loops and the weights on edg...
Cited by 0
École Normale, Supérieure Lyon, École Normale et al. · 1998
Loop fusion is a program transformation that combines several loops into one. It is used in parallelizing compilers mainly for increasing the granularity of loops and for improving data reuse. The goal of this report is to study, from a theoretical point of view, several variants of the loop fusion problem identifying polynomially solvable cases and NP-complete cases and to make thelink between these problems and some scheduling problems that arise from completely di erent areas. We study, among others, the fusion of loops of di erent types, and the fusion of loops when combined with loop shifting.
Cited by 0
Brian P. Hannah · ScholarlyCommons (University of Pennsylvania) · 2008
Herpes simplex virus (HSV) entry into host cells requires the function of the viral envelope glycoprotein (g) B in concert with three other envelope proteins, namely gD and the complex of gH/gL. Glycoprotein D functions in receptor binding and communicates an activation signal to gB and/or to gH/gL to carry out fusion between the viral envelope and cell membranes to release the capsid into the cell and begin the replication process.\nIn this dissertation, I present a detailed mutagenic analysis of the putative HSV gB fusion loops. I mutated each of the fourteen amino acids that comprise the two loops. In a space filling model of the gB structure, it is apparent that the loops form a single structure, with a hydrophobic ridge at its center. This ridge is comprised of several aromatic and hydrophobic amino acids and is surrounded almost exclusively by charged residues. First, I mutated many of the residues that comprise the hydrophobic ridge. I discovered that five hydrophobic amino acids, four from one loop and one from the other are critical for gB function as mutations to any one of them impair fusion. Four of these comprise the hydrophobic ridge. To my surprise, I also discovered that two charged residues that lie outside the hydrophobic ridge are also important for gB function. Their positions suggest they may support insertion of the hydrophobic ridge into target membranes. These results support my hypothesis that the two loops are an important functional domain that operate cooperatively as one structure.\nI expressed several of the point mutants as soluble recombinant gB proteins, and characterized them in several functional assays. I found that mutations of aromatic amino acids to charged ones or charged amino acids to alanines abolished the ability of gB to associate with model liposome membranes. This provides good evidence that these loops are fusion loops that function by inserting into a target membrane. Also, these results suggest that aromatic and charged residues play important roles in target membrane insertion. Other studies have shown that soluble gB can block virus entry, evidence that it interacts with its own entry receptor. A recent report identified a cell surface protein, PILRα, that may fulfill this role. I found that the mutant forms of gB blocked virus entry of virus as efficiently as WT gB, suggesting that the receptor binding region of gB is distinct from the fusion loops. In contrast, these same mutants were significantly impaired in their ability to bind to cells. I suggest that this apparent anomaly may be explained by the possibility that a proportion of gB binds to a surface lipid via the fusion loops. Recently, our lab showed gB and gH/gL interact when triggered for fusion by the addition of soluble gD. In collaboration with another lab member, we show that mutations to the gB fusion loops abrogate gB association with gH/gL.\nIn summary, my results support the concept that gB functions as a fusion protein and that its two fusion loops act in much the same way as do the fusion loops of VSV G or the class II fusion proteins. Five hydrophobic and two charged residues are most important in the function of the gB fusion loops. I propose that loss of target membrane insertion, impairment of cell binding, and abrogation of gB-gH/gL interaction are all possible mechanisms by which mutations to the gB fusion loops inhibit gB dependent fusion. The remaining enigma is why gB cannot carry out fusion on its own but must act in concert with gH/gL. Future studies may provide the answer to that question. (Abstract shortened by UMI.)
Cited by 0Open access
Nimrod Megiddo, Vivek Sarkar · 1997
Article Free Access Share on Optimal weighted loop fusion for parallel programs Authors: Nimrod Megiddo IBM Almaden Research Center and Tel Aviv University IBM Almaden Research Center and Tel Aviv UniversityView Profile , Vivek Sarkar MIT Laboratory for Computer Science and IBM Software Solutions Division MIT Laboratory for Computer Science and IBM Software Solutions DivisionView Profile Authors Info & Claims SPAA '97: Proceedings of the ninth annual ACM symposium on Parallel algorithms and architecturesJune 1997 Pages 282–291https://doi.org/10.1145/258492.258520Online:01 June 1997Publication History 38citation550DownloadsMetricsTotal Citations38Total Downloads550Last 12 Months23Last 6 weeks6 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF
Cited by 64Open access
Yuan Zhao, Qing Yi, Ken Kennedy et al. · OSTI OAI (U.S. Department of Energy Office of Scientific and Technical Information) · 2005
Traditional compilers are limited in their ability to optimize applications for different architectures because statically modeling the effect of specific optimizations on different hardware implementations is difficult. Recent research has been addressing this issue through the use of empirical tuning, which uses trial executions to determine the optimization parameters that are most effective on a particular hardware platform. In this paper, we investigate empirical tuning of loop fusion, an important transformation for optimizing a significant class of real-world applications. In spite of its usefulness, fusion has attracted little attention from previous empirical tuning research, partially because it is much harder to configure than transformations like loop blocking and unrolling. This paper presents novel compiler techniques that extend conventional fusion algorithms to parameterize their output when optimizing a computation, thus allowing the compiler to formulate the entire configuration space for loop fusion using a sequence of integer parameters. The compiler can then employ an external empirical search engine to find the optimal operating point within the space of legal fusion configurations and generate the final optimized code using a simple code transformation system. We have implemented our approach within our compiler infrastructure and conducted preliminary experiments using a simple empirical search strategy. Our results convey new insights on the interaction of loop fusion with limited hardware resources, such as available registers, while confirming conventional wisdom about the effectiveness of loop fusion in improving application performance.
Cited by 15Open access