Class / Patent application number | Description | Number of patent applications / Date published |
717160000 | Including loop | 74 |
20080222623 | Efficient Code Generation Using Loop Peeling for SIMD Loop Code with Multiple Misaligned Statements - An approach is provided for vectorizing misaligned references in compiled code for SIMD architectures that support only aligned loads and stores. In this framework, a loop is first simdized as if the memory unit imposes no alignment constraints. The compiler then inserts data reorganization operations to satisfy the actual alignment requirements of the hardware. Finally, the code generation algorithm generates SIMD codes based on the data reorganization graph, addressing realistic issues such as runtime alignments, unknown loop bounds, residual iteration counts, and multiple statements with arbitrary alignment combinations. Loop peeling is used to reduce the computational overhead associated with misaligned data. A loop prologue and epilogue are peeled from individual iterations in the simdized loop, and vector-splicing instructions are applied to the peeled iterations, while the steady-state loop body incurs no additional computational overhead. | 09-11-2008 |
20080229298 | Compiler Method for Employing Multiple Autonomous Synergistic Processors to Simultaneously Operate on Longer Vectors of Data - A compiler includes a mechanism for employing multiple synergistic processors to execute long vectors. The compiler receives a single source program. The compiler identifies vectorizable loop code in the single source program and extracts the vectorizable loop code from the single source program. The compiler then compiles the extracted vectorizable loop code for a plurality of synergistic processors. The compiler also compiles a remainder of the single source program for a principal processor to form an executable main program such that the executable main program controls operation of the executable vectorizable loop code on the plurality of synergistic processors. | 09-18-2008 |
20080244549 | METHOD AND APPARATUS FOR EXPLOITING THREAD-LEVEL PARALLELISM - According to one example embodiment, there is disclosed herein uses partial recurrence relaxation for parallelizing DOACROSS loops on multi-core computer architectures. By one example definition, a DOACROSS may be a loop that allows successive iterations executing by overlapping; that is, all iterations must impose a partial execution order. According to one embodiment, the inventive subject matter may be used to transform the dependence structure of a given loop with recurrences for maximal degree of thread-level parallelism (TLP), where the threads can be mapped on to either different logical processors (in a hyperthreaded processor) or can be mapped onto different physical cores (or processors) in a multi-core processor. | 10-02-2008 |
20080250401 | Tiling across loop nests with possible recomputation - Described is a technology by which a series of loop nests corresponding to source code are detected by a compiler, with the series of loop nests tiled together, (thereby increasing the ratio of cache hits to misses in a multi-processor environment). The compiler transforms the series of loop nests into a plurality of tile loops within a controller loop, including using dependency analysis to determine which results from a tile loop need to be pre-computed before another tile loop. For dependency analysis, the compiler may use a directed acyclic graph as a high-level intermediate representation, and split the graph into sub-graphs each representing an array. The compiler uses descriptors processed from the graph to determine the controller loop and the tile loops within that controller loop. | 10-09-2008 |
20080271005 | SYSTEM, METHOD AND COMPUTER PROGRAM PRODUCT FOR REDUCING NUMBER OF EXCEPTION CHECKS - Based on operations within an uncounted loop of source code, one or more calculations are generated for determining, at runtime, an expected number of iterations through which the uncounted loop can iterate before encountering an exception corresponding to at least one target exception check. A copy of the uncounted loop omitting each target exception check is generated. The uncounted loop, the copy of the uncounted loop, and the one or more calculations are arranged in compiled code so that at runtime program flow enters the copy of the uncounted loop. If a maximum number of iterations of the copy of the uncounted loop is reached, program flow proceeds from the copy of the uncounted loop to the uncounted loop. The maximum number of iterations is no more than the smallest member of a set consisting of the expected number of iterations for each target exception check. | 10-30-2008 |
20080313621 | SCALAR CODE REDUCTION USING SHORTEST PATH ROUTING - This document discusses, among other things, a system and method computing the shortest path expression in a loop having a plurality of expressions. Candidate expressions in the loop are identified and partitioned into sets. A cost matrix is computed as a function of the sets. Paths are found through the cost matrix and, if there are cycles in the paths, the cycles are broken. One or more shortest path expressions are generated as a function of the paths and one or more of the expressions in the loop are replaced with the shortest path expressions. | 12-18-2008 |
20090055815 | Eliminate Maximum Operation in Loop Bounds with Loop Versioning - A method and computer program product for eliminating maximum and minimum expressions within loop bounds are provided. A loop in a code is identified. The loop is determined to meet conditions, which require an upper loop bound and a lower loop bound to contain maximum and minimum expressions, loop-invariant operands, a predetermined size for a code size, and a total number of instructions to be greater than a predetermined constant. A profitability of loop versioning is determined based on a performance gain of a fast version of the loop, a probability of executing the fast version of the loop at runtime, and an overhead for performing loop versioning. A pair of lower loop bound and upper loop bound values resulting in a constant number is identified. A loop iteration value is checked to be a non-zero constant. Branches are identified, and loop versioning is performed to generate a versioned loop. | 02-26-2009 |
20090064119 | Systems, Methods, And Computer Products For Compiler Support For Aggressive Safe Load Speculation - Systems, methods and computer products for compiler support for aggressive safe load speculation. Exemplary embodiments include a method for aggressive safe load speculation for a compiler in a computer system, the method including building a control flow graph, identifying both countable and non-countable loops, gathering a set of candidate loops for load speculation, for each candidate loop in the set of candidate loops gathered for load speculation performing computing an estimate of the iteration count, delay cycles, and code size, performing a profitability analysis and determine an unroll factor based on the delay cycles and the code size, transforming the loop by generating a prologue loop to achieve data alignment and an unrolled main loop with loop directives, indicating which loads can safely be executed speculatively and performing low-level instruction on the generated unrolled main loop. | 03-05-2009 |
20090064120 | Method and apparatus to achieve maximum outer level parallelism of a loop - In one embodiment, the present invention includes a method for constructing a data dependency graph (DDG) for a loop to be transformed, performing statement shifting to transform the loop into a first transformed loop according to at least one of first and second algorithms, performing unimodular and echelon transformations of a selected one of the first or second transformed loops, partitioning the selected transformed loop to obtain maximum outer level parallelism (MOLP), and partitioning the selected transformed loop into multiple sub-loops. Other embodiments are described and claimed. | 03-05-2009 |
20090077544 | METHOD, SYSTEM AND PROGRAM PRODUCT FOR OPTIMIZING EMULATION OF A SUSPECTED MALWARE - A method, system and program product for optimizing emulation of a suspected malware. The method includes identifying, using an emulation optimizer tool, whether an instruction in a suspected malware being emulated by an emulation engine in a virtual environment signifies a long loop and, if so, generating a first hash for the loop. Further, the method includes ascertaining whether the first hash generated matches any long loop entries in a storage and, if so calculating a second hash for the long loop. Furthermore, the method includes inspecting any long loop entries ascertained to find an entry having a respective second hash matching the second hash calculated. If an entry matching the second hash calculated is found, the method further includes updating one or more states of the emulation engine, such that, execution of the long loop of the suspected malware is skipped, which optimizes emulation of the suspected malware. | 03-19-2009 |
20090077545 | PIPELINED PARALLELIZATION OF MULTI-DIMENSIONAL LOOPS WITH MULTIPLE DATA DEPENDENCIES - A mechanism for folding all the data dependencies in a loop into a single, conservative dependence. This mechanism leads to one pair of synchronization primitives per loop. This mechanism does not require complicated, multi-stage compile time analysis. This mechanism considers only the data dependence information in the loop. The low synchronization cost balances the loss in parallelism due to the reduced overlap between iterations. Additionally, a novel scheme is presented to implement required synchronization to enforce data dependences in a DOACROSS loop. The synchronization is based on an iteration vector, which identifies a spatial position in the iteration space of the loop. Multiple iterations executing in parallel have their own iteration vector for synchronization where they update their position in the iteration space. As no sequential updates to the synchronization variable exist, this method exploits a greater degree of parallelism. | 03-19-2009 |
20090083724 | System and Method for Advanced Polyhedral Loop Transformations of Source Code in a Compiler - A system and method for advanced polyhedral loop transformations of source code in a compiler are provided. The mechanisms of the illustrative embodiments address the weaknesses of the known polyhedral loop transformation based approaches by providing mechanisms for performing code generation transformations on individual statement instances in an intermediate representation generated by the polyhedral loop transformation optimization of the source code. These code generation transformations have the important property that they do not change program order of the statements in the intermediate representation. This property allows the result of the code generation transformations to be provided back to the polyhedral loop transformation mechanisms in a program statement view, via a new re-entrance path of the illustrative embodiments, for additional optimization. | 03-26-2009 |
20090288075 | PARALLELIZING NON-COUNTABLE LOOPS WITH HARDWARE TRANSACTIONAL MEMORY - A system and method for speculatively parallelizing non-countable loops in a multi-threaded application. A multi-core processor receives instructions for a multi-threaded application. The application may contain non-countable loops. Non-countable loops have an iteration count value that cannot be determined prior to the execution of the non-countable loop, a loop index value that cannot be non-speculatively determined prior to the execution of an iteration of the non-countable loop, and control that is not transferred out of the loop body by a code line in the loop body. The compiler replaces the non-countable loop with a parallelized loop pattern that uses outlined function calls defined in a parallelization library (PL) in order to speculatively execute iterations of the parallelized loop. The parallelized loop pattern is configured to squash and re-execute any speculative thread of the parallelized loop pattern that is signaled to have a transaction failure. | 11-19-2009 |
20090307673 | System and Method for Domain Stretching for an Advanced Dual-Representation Polyhedral Loop Transformation Framework - A system and method for domain stretching for an advanced dual-representation polyhedral loop transformation framework are provided. The mechanisms of the illustrative embodiments address the weaknesses of the known polyhedral loop transformation based approaches by providing mechanisms for performing code generation transformations on individual statement instances in an intermediate representation generated by the polyhedral loop transformation optimization of the source code. These code generation transformations have the important property that they do not change program order of the statements in the intermediate representation. This property allows the result of the code generation transformations to be provided back to the polyhedral loop transformation mechanisms in a program statement view, via a new re-entrance path of the illustrative embodiments, for additional optimization. In addition, mechanisms are provided for stretching the domains of statements in a program loop view of the source code to thereby normalize the domains. | 12-10-2009 |
20090307674 | IMPROVING DATA LOCALITY AND PARALLELISM BY CODE REPLICATION AND ARRAY CONTRACTION - Provided are a method, system, and article of manufacture improving data locality and parallelism by code replication and array contraction. Source code including an array of elements referenced using at least two indices is processed. The array is nested within multiple loops, wherein at least two of the loops perform iterations with respect to the indices of the array, wherein the index incremented in at least one innermost loop of the loops does not comprise a leftmost index in the array. The source code is transformed to object code by performing operations including fusing at least two innermost loops of the loops in object code generated by compiling the source code by replicating statements from at least one of the innermost loops into a fused innermost loop and performing loop interchange in the object code to have the fused innermost loop provide iterations with respect to the leftmost index in the array. | 12-10-2009 |
20090307675 | DATA DEPENDENCE TESTING FOR LOOP FUSION WITH CODE REPLICATION, ARRAY CONTRACTION, AND LOOP INTERCHANGE - Methods and apparatus to data dependence testing for loop fusion, e.g., with code replication, array contraction, and/or loop interchange, are described. In one embodiment, a compiler may optimize code for efficient execution during run-time by testing for dependencies associated with improving memory locality through code replication in loops that enable various loop transformations. Other embodiments are also described. | 12-10-2009 |
20090328020 | INTERFACE OPTIMIZATION IN A CLOSED SYSTEM - Interface optimization is provided using a closed system in which all the individual software components in the system are known to the compiler at a single point in time. This knowledge enables significant opportunities to optimize the implementation of interfaces on a set of implemented objects. When code is compiled, because the compiler knows the full list of interfaces and the objects which implement the interfaces, it can improve execution and working set (i.e., recently referenced pages in a program's virtual address space) when implementing the interfaces on objects. This improvement may be realized by reducing the size of interface lookup tables which map each interface to the object types which implement that particular interface. | 12-31-2009 |
20090328021 | Multiversioning if statement merging and loop fusion - In one embodiment of the invention, a method for fusing a first loop nested in a first IF statement with a second loop nested in a second IF statement without the use of modified and referenced (mod-ref) information to determine if certain conditional statements in the IF statements retain variable values. | 12-31-2009 |
20100023932 | Efficient Software Cache Accessing With Handle Reuse - A mechanism for efficient software cache accessing with handle reuse is provided. The mechanism groups references in source code into a reference stream with the reference stream having a size equal to or less than a size of a software cache line. The source code is transformed into optimized code by modifying the source code to include code for performing at most two cache lookup operations for the reference stream to obtain two cache line handles. Moreover, the transformation involves inserting code to resolve references in the reference stream based on the two cache line handles. The optimized code may be output for generation of executable code. | 01-28-2010 |
20100146495 | METHOD AND SYSTEM FOR INTERPROCEDURAL PREFETCHING - A computing system has an amount of shared cache, and performs runtime automatic parallelization wherein when a parallelized loop is encountered, a main thread shares the workload with at least one other non-main thread. A method for providing interprocedural prefetching includes compiling source code to produce compiled code having a main thread including a parallelized loop. Prior to the parallelized loop in the main thread, the main thread includes prefetching instructions for the at least one other non-main thread that shares the workload of the parallelized loop. As a result, the main thread prefetches data into the shared cache for use by the at least one other non-main thread. | 06-10-2010 |
20100205592 | CONTROL STRUCTURE REFINEMENT OF LOOPS USING STATIC ANALYSIS - A system and method for discovering a set of possible iteration sequences for a given loop in a software program is described, to transform the loop representation. In a program containing a loop, the loop is partitioned into a plurality of portions based on splitting criteria. Labels are associated with the portions, and an initial loop automaton is constructed that represents the loop iterations as a regular language over the labels corresponding to the portions in the program. Subsequences of the labels are analyzed to determine infeasibility of the subsequences permitted in the automaton. The automaton is refined by removing all infeasible subsequences to discover a set of possible iteration sequences in the loop. The resulting loop automaton is used in a subsequent program verification or analysis technique to find violations of correctness properties in programs. | 08-12-2010 |
20100318979 | VECTOR ATOMIC MEMORY OPERATION VECTOR UPDATE SYSTEM AND METHOD - A system and method of compiling program code, wherein the program code includes an operation on an array of data elements stored in memory of a computer system. The program code is scanned for an equation which may have recurring data points. The equation is then replaced with vectorized machine executable code, wherein the machine executable code comprises a nested loop and wherein the nested loop comprises an exterior loop and a virtual interior loop. The exterior loop decomposes the equation into a plurality of loops of length N, wherein N is an integer greater than one. The virtual interior loop executes vector operations corresponding to the N length loop to form a result vector resident in memory, wherein the virtual interior loop includes a vector atomic memory operation (AMO) instruction. | 12-16-2010 |
20100318980 | STATIC PROGRAM REDUCTION FOR COMPLEXITY ANALYSIS - Described is an analysis tool/techniques for determining the computational complexity of a computer program, including when the program includes procedures having nested loops and/or multi-path loops. First, multi-path loops are converted into code-fragments consisting of simpler loops via a transformation called control flow refinement. Progress invariants are determined for appropriate locations in the procedure to represent relationships between a state that can arise at that program location and the previous state at that location. A bound finding mechanism (such as one based on pattern matching) is then used to compute loop bounds from progress invariants. These bounds are then composed appropriately to determine a precise bound for the enclosing procedure. | 12-16-2010 |
20110029962 | VECTORIZATION OF PROGRAM CODE - A method for vectorization of a block of code is provided. The method comprises receiving a first block of code as input; and converting the first block of code into at least a second block of code and a third block of code. The first block of code accesses a first set of memory addresses that are potentially misaligned. The second block of code performs conditional leaping address incrementation to selectively access a first subset of the first set of memory addresses. The third block of code accesses a second subset of the first set of memory addresses starting from an aligned memory address, simultaneously accessing multiple memory addresses at a time. No memory address belongs to both the first subset and the second subset of memory addresses. | 02-03-2011 |
20110047534 | PROACTIVE LOOP FUSION OF NON-ADJACENT LOOPS WITH INTERVENING CONTROL FLOW INSTRUCTIONS - A system and method for optimization of code with non-adjacent loops. A compiler builds a node tree, which is not a control flow graph, that represents parent-child relationships of nodes of a computer program. Each node represents a control flow statement or a straight-line block of statements of the computer program. If a non-adjacent loop pair of nodes satisfy predetermined conditions, the compiler may perform legal code transformations on the computer program and corresponding node transformations on the node tree. These transformations may make adjacent this pair of loop nodes. The compiler may be configured to perform legal code transformations, such as head and tail duplication, code motion, and if-merging, in order to make adjacent these two loop nodes. Then loop fusion may be performed on this loop pair in order to increase instruction level parallelism (ILP) within an optimized version of the original source code. | 02-24-2011 |
20110185347 | METHOD AND SYSTEM FOR EXECUTION PROFILING USING LOOP COUNT VARIANCE - A method for executing a computer program involving obtaining a statement of the source code, where the statement comprises a method call, and where the source code is composed in a statically-typed programming language. The method also involves, upon entry into a loop included in the computer program: incrementing an entry counter by one; and, for each iteration of the loop, incrementing an iteration counter by one, incrementing a local counter by one to obtain an incremented value of the local counter, incrementing a summation variable by the incremented value of the local counter, and executing the iteration of the loop. | 07-28-2011 |
20110225573 | Computation Reuse for Loops with Irregular Accesses - A compiler selects a nested loop within software code that includes an outer loop and an inner loop. The outer loop includes an outer induction variable and the inner loop includes an inner induction variable. The compiler identifies a computation included in the nested loop that generates an irregular array access, which includes an expression of both the outer induction variable and the inner induction variable. Next, the compiler identifies a redundant calculation for the computation based upon the outer induction variable and the inner induction variable, and generates a temporary variable to correspond with the redundant calculation. The compiler replaces the computation with the temporary variable in the nested loop and, in turn, compiles the nested loop with the included temporary variable. | 09-15-2011 |
20110231830 | Loop Transformation for Computer Compiler Optimization - A new computer-compiler architecture includes code analysis processes in which loops present in an intermediate instruction set are transformed into more efficient loops prior to fully executing the intermediate instruction set. The compiler architecture starts by generating the equivalent intermediate instructions for the original high level source code. For each loop in the intermediate instructions, a total cycle cost is calculated using a cycle cost table associated with the compiler. The compiler then generates intermediate code for replacement loops in which all conversion instructions are removed. The cycle costs for these new transformed loops are then compared against the total cycle cost for the original loops. If the total cycle costs exceed the new cycle costs, the compiler will replace the original loops in the intermediate instructions with the new transformed loops prior to generation of final code using the instruction set of the processor. | 09-22-2011 |
20110271265 | METHOD OF AUTOMATIC GENERATION OF EXECUTABLE CODE FOR MULTI-CORE PARALLEL PROCESSING - A system, method and computer program product for optimizing the process of compilation of computer program code. The compiler transforms the program code written in a variety of languages and creates additional code performing parallel processing of program tasks on target hardware architecture. The transformation of code is performed to achieve optimization of various critical parameters such as the execution speed on a multi-core or cluster target hardware architecture. | 11-03-2011 |
20110314461 | IMPLEMENTING PARALLEL LOOPS WITH SERIAL SEMANTICS - The present invention extends to methods, systems, and computer program products for implementing parallel loops with serial semantics. Embodiments of the invention provide a semantic transforms and codegen patterns that provide more efficient parallel loop implementations with serial loop semantics. Embodiments of the invention support assignments within for-loop bodies, support break/return constructs within for-loop bodies, and run transformations to covert serial constructs to parallel constructs. | 12-22-2011 |
20120079469 | Systems And Methods For Compiler-Based Vectorization Of Non-Leaf Code - Systems and methods for the vectorization of software applications are described. In some embodiments, source code dependencies can be expressed in ways that can extend a compiler's ability to vectorize otherwise scalar functions. For example, when compiling a called function, a compiler may identify dependencies of the called function on variables other than parameters passed to the called function. The compiler may record these dependencies, e.g., in a dependency file. Later, when compiling a calling function that calls the called function, the same (or another) compiler may reference the previously-identified dependencies and use them to determine whether and how to vectorize the calling function. In particular, these techniques may facilitate the vectorization of non-leaf loops. Because non-leaf loops are relatively common, the techniques described herein can increase the amount of vectorization that can be applied to many applications. | 03-29-2012 |
20120117552 | SPECULATIVE COMPILATION TO GENERATE ADVICE MESSAGES - Methods to improve optimization of compilation are presented. In one embodiment, a method includes identifying one or more optimization speculations with respect to a code region and speculatively performing transformation on an intermediate representation of the code region in accordance with an optimization speculation. The method includes generating an advice message corresponding to the optimization speculation and displaying the advice message if the optimization speculation results in an improved compilation result. | 05-10-2012 |
20120151463 | METHOD AND SYSTEM FOR UTILIZING PARALLELISM ACROSS LOOPS - A method for compiling application source code that includes selecting multiple loops for parallelization. The multiple loops include a first loop and a second loop. The method further includes partitioning the first loop into a first set of chunks, partitioning the second loop into a second set of chunks, and calculating data dependencies between the first set of chunks and the second set of chunks. A first chunk of the second set of chunks is dependent on a first chunk of the first set of chunks. The method further includes inserting, into the first loop and prior to completing compilation, a precedent synchronization instruction for execution when execution of the first chunk of the first set of chunks completes, and completing the compilation of the application source code to create an application compiled code. | 06-14-2012 |
20120167068 | SPECULATIVE REGION-LEVEL LOOP OPTIMIZATIONS - A system and method are configured to apply region level optimizations to a selected region of source code rather than loop level optimizations to a loop or loop nest. The region may include an outer loop, a plurality of inner loops and at least one control code. If the region includes an exceptional control flow statement and/or a procedure call, speculative region-level multi-versioning may be applied. | 06-28-2012 |
20120167069 | LOOP PARALLELIZATION BASED ON LOOP SPLITTING OR INDEX ARRAY - Methods and apparatus to provide loop parallelization based on loop splitting and/or index array are described. In one embodiment, one or more split loops, corresponding to an original loop, are generated based on the mis-speculation information. In another embodiment, a plurality of subloops are generated from an original loop based on an index array. Other embodiments are also described. | 06-28-2012 |
20120331453 | VECTORIZATION OF PROGRAM CODE - A method for vectorization of a block of code is provided. The method comprises receiving a first block of code as input; and converting the first block of code into at least a second block of code and a third block of code. The first block of code accesses a first set of memory addresses that are potentially misaligned. The second block of code performs conditional leaping address incrementation to selectively access a first subset of the first set of memory addresses. The third block of code accesses a second subset of the first set of memory addresses starting from an aligned memory address, simultaneously accessing multiple memory addresses at a time. No memory address belongs to both the first subset and the second subset of memory addresses. | 12-27-2012 |
20130117737 | DEMAND-DRIVEN ALGORITHM TO REDUCE SIGN-EXTENSION INSTRUCTIONS INCLUDED IN LOOPS OF A 64-BIT COMPUTER PROGRAM - One embodiment of the present invention sets forth a technique for reducing sign-extension instructions (SEIs) included in a computer program, the technique involves receiving intermediate code that is associated with the computer program and includes a first SEI that is included in a loop structure within the computer program, determining that the first SEI is eligible to be moved outside of the loop structure, inserting into a preheader of the loop a second SEI that, when executed by a processor, promotes an original value targeted by the first SEI from a smaller type to a larger type, and replacing the first SEI with one or more intermediate instructions that are eligible for additional compiler optimizations. | 05-09-2013 |
20130125104 | REDUCING BRANCH MISPREDICTION IMPACT IN NESTED LOOP CODE - According to one aspect of the present disclosure, a method and technique for reducing branch misprediction impact for nested loop code is disclosed. The method includes: responsive to identifying code having an outer loop and an inner loop, determining a quantity of iterations of the inner loop for an initial number of iterations of the outer loop; determining a number of processor cycles for executing the quantity of iterations of the inner loop for the initial number of iterations of the outer loop; determining whether the number of processor cycles is less than a threshold; and responsive to determining that the number of processor cycles is less than the threshold, fully unrolling the inner loop for the initial number of iterations of the outer loop. | 05-16-2013 |
20130125105 | UNIFIED PARALLEL C WORK-SHARING LOOP CONSTRUCT TRANSFORMATION - Control flow information and data flow information associated with a program containing a upc_forall loop are built. A shared reference map data structure using the control flow information and the data flow information is created. All local shared accesses are hashed to facilitate a constant access stride after being rewritten. All local shared references in a hash entry having a longest list are privatized. The upc_forall loop is rewritten into a for loop. Responsive to a determination that an unprocessed upc_forall loop does not exist, dead store elimination is run. The control flow information and the data flow information associated with the program containing the for loop is rebuilt. | 05-16-2013 |
20130167130 | Data Prefetching and Coalescing for Partitioned Global Address Space Languages - An illustrative embodiment of a computer-implemented process for shared data prefetching and coalescing optimization versions a loop containing one or more shared references into an optimized loop and an un-optimized loop, transforms the optimized loop into a set of loops, and stores shared access associated information of the loop using a prologue loop in the set of loops. The shared access associated information pertains to remote data and is collected using the prologue loop in absence of network communication and builds a hash table. An associated data structure is updated each time the hash table is entered, and is sorted to remove duplicate entries and create a reduced data structure. Patterns across entries of the reduced data structure are identified and entries are coalesced. Data associated with a coalesced entry is pre-fetched using a single communication and a local buffer is populated with the fetched data for reuse. | 06-27-2013 |
20130227537 | CONTROL STRUCTURE REFINEMENT OF LOOPS USING STATIC ANALYSIS - A system and method for discovering a set of possible iteration sequences for a given loop in a software program is described, to transform the loop representation. In a program containing a loop, the loop is partitioned into a plurality of portions based on splitting criteria. Labels are associated with the portions, and an initial loop automaton is constructed that represents the loop iterations as a regular language over the labels corresponding to the portions in the program. Subsequences of the labels are analyzed to determine infeasibility of the subsequences permitted in the automaton. The automaton is refined by removing all infeasible subsequences to discover a set of possible iteration sequences in the loop. The resulting loop automaton is used in a subsequent program verification or analysis technique to find violations of correctness properties in programs. | 08-29-2013 |
20130290943 | METHODS TO OPTIMIZE A PROGRAM LOOP VIA VECTOR INSTRUCTIONS USING A SHUFFLE TABLE AND A BLEND TABLE - According to one embodiment, a code optimizer is configured to receive first code having a program loop implemented with scalar instructions to store values of a first array to a second array based on values of a third array and to generate second code representing the program loop using at least one vector instruction. The second code include a shuffle instruction to shuffle elements of the first array based on the third array using a shuffle table in a vector manner, a blend instruction to blend the shuffled elements of the first array using a blend table in a vector manner, and a store instruction to store the blended elements of the first array in the second array. | 10-31-2013 |
20140096119 | LOOP VECTORIZATION METHODS AND APPARATUS - Loop vectorization methods and apparatus are disclosed. An example method includes setting a dynamic adjustment value of a vectorization loop; executing the vectorization loop to vectorize a loop by grouping iterations of the loop into one or more vectors; identifying a dependency between iterations of the loop as; and setting the dynamic adjustment value based on the identified dependency. | 04-03-2014 |
20140115569 | ADAPTIVE INSTRUCTION PREFETCHING AND FETCHING MEMORY SYSTEM APPARATUS AND METHOD FOR MICROPROCESSOR SYSTEM - A method and system of the instruction packing and scaling are designed for simultaneously enhancing energy efficiency by concurrent and advanced prefetching/fetching instructions via the small and/or banked caches and for improving the performance of microprocessors by reducing the fraction of program and by employing the simple and fast caches. The invention is also designed for converting high fraction code to simplified, branch-reduced, and hidden code during compilation time, for storing packed/scaled code to concurrently accessible the plurality of caches and main memories, and for reverting the code to the native instructions during the instruction prefetch and fetch operations. Consequently, the invention does not forward many flow control instructions including procedure callers/returns and unconditional branches to microprocessors. In particular, the invention accurately prefetches/fetches instructions from the main memories to small, simple, and fast caches, which significantly reduce leakage and dynamic power dissipation, access time, and chip area. | 04-24-2014 |
20140173576 | Loop Invariant Method Expression Hoisting - A system, method and computer-readable medium are disclosed for improving the performance of a compiler. A set of source code instructions are processed to generate a plurality of source code instruction subsets, each of which is respectively associated with a mathematical operator. The source code subsets are then reordered to “hoist,” or place, a source code instruction subset associated with a product operator before a source code instruction subset associated with a summation operator. The plurality of source code instruction subsets are iteratively reordered until no source code instruction subset associated with a summation operator precedes a source code instruction subset associated with a product operator. A compiler is then used to compile the resulting reordered plurality of source code instruction subsets into a set of optimized object code instructions. | 06-19-2014 |
20140189666 | AUTOMATIC PIPELINE COMPOSITION - A method and apparatus for automatic pipeline are provided herein. Syntax elements may be manually inserted into the code, or automatically injected into the code. The syntax elements may specify hints such as data type parameters to independent functions allowing the functions to be automatically coalesced into a single loop, providing optimized data accesses to be coalesced for each function in the pipeline within the single loop. A run-time system produces optimized machine code for a target processor using syntax elements to guide the optimizations. Additionally, the pipeline may be executed. The pipeline includes the coalesced functions and data accesses. | 07-03-2014 |
20140189667 | SPECULATIVE MEMORY DISAMBIGUATION ANALYSIS AND OPTIMIZATION WITH HARDWARE SUPPORT - Methods and apparatus to provide speculative memory disambiguation analysis and optimization with hardware support are described. In one embodiment, input code is analyzed to determine one or more memory locations to be accessed by the input program and output code is generated based on the input code and one or more assumptions about invariance of the one or more memory locations. The output code is generated also based on hardware transactional memory support and hardware dynamic disambiguation support. Other embodiments are also described. | 07-03-2014 |
20140237460 | VECTORIZATION IN AN OPTIMIZING COMPILER - An optimizing compiler includes a vectorization mechanism that optimizes a computer program by substituting code that includes one or more vector instructions (vectorized code) for one or more scalar instructions. The cost of the vectorized code is compared to the cost of the code with only scalar instructions. When the cost of the vectorized code is less than the cost of the code with only scalar instructions, the vectorization mechanism determines whether the vectorized code will likely result in processor stalls. If not, the vectorization mechanism substitutes the vectorized code for the code with only scalar instructions. When the vectorized code will likely result in processor stalls, the vectorization mechanism does not substitute the vectorized code, and the code with only scalar instructions remains in the computer program. | 08-21-2014 |
20140331216 | APPARATUS AND METHOD FOR TRANSLATING MULTITHREAD PROGRAM CODE - A method and apparatus for translating a multithread program code are provided. The method includes: dividing a multithread program code into a plurality of statements according to a synchronization point; generating at least one loop group by combining one or more adjacent statements based on a number of instructions included in the plurality of statements; expanding or renaming variables in each of the plurality of statements so that each statement included in the at least one loop group is executed with respect to a work item of a different work group; and enclosing each of the generated at least one loop group respectively with a work item coalescing loop. | 11-06-2014 |
20140344795 | COMPUTER-READABLE RECORDING MEDIUM, COMPILING METHOD, AND INFORMATION PROCESSING APPARATUS - A compiler determines executability of loop fusion, for each of a plurality of loops existing in a code to be processed, based on performance information of a system where the code to be processed is executed and based on operands and number of data transfers executed inside each of the loops. Then, the compiler executes fusion of loop processing in accordance with a determination result of executability of the loop fusion. | 11-20-2014 |
20150067662 | COMPUTER SYSTEM AND A METHOD FOR GENERATING AN OPTIMIZED PROGRAM CODE - A computer system for generating an optimized program code from a program code having a loop with an exit branch, wherein the computer system comprises a processing unit, wherein the processing unit is arranged to convert an exit instruction of the exit branch into a predicated exit instruction, wherein the processing unit is arranged to determine common dependencies within the loop, wherein the processing unit is arranged to generate modified dependencies by adding additional dependencies to the common dependencies, and wherein the processing unit is arranged to apply an algorithm that uses software pipelining for generating an optimized program code for the loop based on the modified dependencies. | 03-05-2015 |
20150089485 | SYSTEM AND METHOD FOR GENERATION OF EVENT DRIVEN, TUPLE-SPACE BASED PROGRAMS - In a system for automatic generation of event-driven, tuple-space based programs from a sequential specification, a hierarchical mapping solution can target different runtimes relying on event-driven tasks (EDTs). The solution uses loop types to encode short, transitive relations among EDTs that can be evaluated efficiently at runtime. Specifically, permutable loops translate immediately into conservative point-to-point synchronizations of distance one. A runtime-agnostic which can be used to target the transformed code to different runtimes. | 03-26-2015 |
20150095897 | METHOD AND APPARATUS FOR CONVERTING PROGRAMS - Methods and apparatuses of converting a program, which may enhance an execution speed of a computer program, are provided. The method may include receiving a program, detecting at least one loop statement including at least one branch statement within the program, determining whether the loop statement may be split into at one or more sub-loop statements which perform the same function as a function of the loop statement and from which the branch statement has been removed, splitting the loop statement into the sub-loop statements and removing the branch statement included in the loop statement if it is determined that the loop statement may be split as a result of the determination, and outputting a result of removing the branch statement. | 04-02-2015 |
20150106798 | SHARING DYNAMIC VARIABLES IN A HIGH AVAILABILITY ENVIRONMENT - Methods and systems are provided that utilize compiler technology in identifying changed critical variables in work assignment code that cause synchronization issues between a master system and another server. The identified changed critical variables are shared by the master server in a high availability environment. In general, the sharing of changed critical variables includes sending, via a master system, changed code or critical variables to a receiving system. The receiving system can implement the changed code or critical variables to maintain synchronization with the master system. | 04-16-2015 |
20150309778 | SYSTEMS AND METHODS FOR APPROXIMATION BASED OPTIMIZATION OF DATA PROCESSORS - A compilation system can apply a smoothness constraint to the arguments of a compute-bound function invoked in a software program, to ensure that the value(s) of one or more function arguments are within specified respective threshold(s) from selected nominal value(s). If the constraint is satisfied, the function invocation is replaced with an approximation thereof. The smoothness constraint may be determined for a range of value(s) of function argument(s) so as to determine a neighborhood within which the function can be replaced with an approximation thereof. The replacement of the function with an approximation thereof can facilitate simultaneous optimization of computation accuracy, performance, and energy/power consumption. | 10-29-2015 |
20160048380 | PROGRAM OPTIMIZATION METHOD, PROGRAM OPTIMIZATION PROGRAM, AND PROGRAM OPTIMIZATION APPARATUS - A program optimization method, executed by an arithmetic processing device, includes collecting profile information including a runtime analysis result by causing a computer to execute an original program to be optimized, calculating a calculation wait time based on the profile information, and generating a tuned-up program, when the calculation wait time is longer than a first threshold, by inserting an SIMD operation control line that performs an SIMD operation for an instruction in IF statement in the loop when an SIMD instruction ratio in the loop in the original program is lower than a second threshold. | 02-18-2016 |
20160110171 | COMPILER OPTIMIZATION FOR COMPLEX EXPONENTIAL CALCULATIONS - Technologies for optimizing complex exponential calculations include a computing device with optimizing compiler. The compiler parses source code, optimizes the parsed representation of the source code, and generates output code. During optimization, the compiler identifies a loop in the source code including a call to the exponential function having an argument that is a loop-invariant complex number multiplied by the loop index variable. The compiler tiles the loop to generate a pair of nested loops. The compiler generates code to pre-compute the exponential function and store the resulting values in a pair of coefficient arrays. The size of each coefficient array may be equal to the square root of the number of loop iterations. The compiler applies rewrite rules to replace the exponential function call with a multiplicative expression of one element from each of the coefficient arrays. Other embodiments are described and claimed. | 04-21-2016 |
20160139897 | LOOP VECTORIZATION METHODS AND APPARATUS - Loop vectorization methods and apparatus are disclosed. An example method includes prior to executing an original loop having iterations, analyzing, via a processor, the iterations of the original loop, identifying a dependency between a first one of the iterations of the original loop and a second one of the iterations of the original loop, after identifying the dependency, vectorizing a first group of the iterations of the original loop based on the identified dependency to form a vectorization loop, and setting a dynamic adjustment value of the vectorization loop based on the identified dependency. | 05-19-2016 |
20160154638 | METHODS AND SYSTEMS TO VECTORIZE SCALAR COMPUTER PROGRAM LOOPS HAVING LOOP-CARRIED DEPENDENCES | 06-02-2016 |
20180024822 | PARTIAL CONNECTION OF ITERATIONS DURING LOOP UNROLLING | 01-25-2018 |
717161000 | Including scheduling instructions | 14 |
20080201698 | Reordering application code to improve processing performance - A method of reordering a sequence of code for processing by a target data processor in order to reduce an execution time for said code on said target data processor is disclosed. The method comprises the steps of: in response to a request to execute said sequence of code, loading said sequence of code into a volatile data store associated with said target data processor; analyzing said sequence of code in relation to properties of said target data processor; identifying interlocks within said sequence of code when executing on said target data processor, in which a portion of code would be stalled while waiting for an earlier portion to complete; reordering said sequence of code to remove at least some of said interlocks; and executing said reordered sequence of code; wherein said steps of analyzing, identifying, reordering and executing are performed by said target data processor. | 08-21-2008 |
20080201699 | Efficient Data Reorganization to Satisfy Data Alignment Constraints - Vectorizing misaligned references in compiled code for SIMD architectures that support only aligned loads and stores is presented. In the framework presented herein, a loop is first simdized as if the memory unit imposes no alignment constraints. The compiler then inserts data reorganization operations to satisfy the actual alignment requirement of the hardware. Finally, the code generation algorithm generates SIMD codes based on the data reorganization graph, addressing realistic issues such as runtime alignments, unknown loop bounds, residue iteration counts, and multiple statements with arbitrary alignment combinations. Beyond generating a valid simdization, a preferred embodiment further improves the quality of the generated codes. Four stream-shift placement policies are disclosed, which minimize the number of data reorganization generated by the alignment handling. | 08-21-2008 |
20080313622 | Low-Level Connectivity Admission Control for Networked Consumer Storage Devices - The present invention relates to a device and a method of accessing a storage of a storage device by reading or writing data to said storage device, wherein said accessing is controlled by an external data controller via a low level in a software stack of said device, and wherein said storage device is accessed without hampering the operation of functionalities at a higher level of said software stack of said device, said device comprises an intermediate storage, and the method comprises the steps of storing commands related to said accessing of data in said intermediate storage as a command queue, executing said commands in said command queue when allowed by a command queue scheduler, said scheduler scheduling in dependence of at least one of the functionalities at said higher level of said software stack. Thereby full control is obtained on storage medium requests by the scheduler. | 12-18-2008 |
20090013316 | Extension of Swing Modulo Scheduling to Evenly Distribute Uniform Strongly Connected Components - A method, apparatus, and computer instructions for scheduling instructions for execution. Identify a series of instructions in a loop, wherein the series of instructions has a cyclic data dependency. Determine whether the series of instructions is a uniform series of instructions. Schedule execution of the uniform series of instructions within the loop to optimize execution of the loop in response to the identified series of instructions being the uniform series of instructions. | 01-08-2009 |
20090064121 | SYSTEMS, METHODS, AND COMPUTER PRODUCTS FOR IMPLEMENTING SHADOW VERSIONING TO IMPROVE DATA DEPENDENCE ANALYSIS FOR INSTRUCTION SCHEDULING - Systems, methods and computer products for implementing shadow versioning to improve data dependence analysis for instruction scheduling. Exemplary embodiments include a method to identify loops within the code to be compiled, for each loop a dependence initializing a matrix, for each loop shadow identifying symbols that are accessed by the loop, examining dependencies, storing, comparing and classifying the dependence vectors, generating new shadow symbols, replacing the old shadow symbols with the new shadow symbols, generating alias relationships between the newly created shadow symbols, scheduling instructions and compiling the code. | 03-05-2009 |
20090138864 | Method and Apparatus for Automatic Second-Order Predictive Commoning - A method and apparatus for automatic second-order predictive commoning is provided by the present invention. During an analysis phase, the intermediate representation of a program code is analyzed to identify opportunities for second-order predictive commoning optimization. The analyzed information is used by the present invention for apply transformations to the program code, such that the number of memory access and the number of computations are reduced for loop iterations and performance of program code is improved. | 05-28-2009 |
20090217253 | COMPILER FRAMEWORK FOR SPECULATIVE AUTOMATIC PARALLELIZATION WITH TRANSACTIONAL MEMORY - A computer program is speculatively parallelized with transactional memory by scoping program variables at compile time, and inserting code into the program at compile time. Determinations of the scoping can be based on whether scalar variables being scoped are involved in inter-loop non-reduction data dependencies, are used outside loops in which they were defined, and at what point in a loop a scalar variable is defined. The inserted code can include instructions for execution at a run time of the program to determine loop boundaries of the program, and issue checkpoint instructions and commit instructions that encompass transaction regions in the program. A transaction region can include an original function of the program and a spin-waiting loop with a non-transactional load, wherein the spin-waiting loop is configured to wait for a previous thread to commit before the current transaction commits. | 08-27-2009 |
20090254895 | Prefetching Irregular Data References for Software Controlled Caches - Prefetching irregular memory references into a software controlled cache is provided. A compiler analyzes source code to identify at least one of a plurality of loops that contain an irregular memory reference. The compiler determines if the irregular memory reference within the at least one loop is a candidate for optimization. Responsive to an indication that the irregular memory reference may be optimized, the compiler determines if the irregular memory reference is valid for prefetching. Responsive to an indication that the irregular memory reference is valid for prefetching, a store statement for an address of the irregular memory reference is inserted into the at least one loop. A runtime library call is inserted into a prefetch runtime library for the irregular memory reference. Data associated with the irregular memory reference is prefetched into the software controlled cache when the runtime library call is invoked. | 10-08-2009 |
20100107147 | COMPILER AND COMPILING METHOD - A compiler allocates an unroll_group_number conferred based on a sequence in which a loop body is replicated by loop unrolling to each loop body during loop unrolling based on the optimized number of loop unrolling. The allocated unroll_group_number is added to each instruction included in each loop body. A priority of an instruction is adjusted based on the allocated unroll_group_number during instruction scheduling. | 04-29-2010 |
20100251229 | PROCESSORS AND COMPILING METHODS FOR PROCESSORS - A compiling method compiles an object program to be executed by a processor having a plurality of execution units operable in parallel. In the method a first availability chain is created from a producer instruction (p | 09-30-2010 |
20120192169 | Optimizing Libraries for Validating C++ Programs Using Symbolic Execution - Particular embodiments optimize a C++ function comprising one or more loops for symbolic execution, comprising for each loop, if there is a branching condition within the loop, then rewrite the loop to move the branching condition outside the loop. Particular embodiments may further optimize the C++ function through simplified symbolic expressions and adding constructs forcing delayed interpretation of symbolic expressions during the symbolic execution. | 07-26-2012 |
20130111453 | THROUGHPUT-AWARE SOFTWARE PIPELINING FOR HIGHLY MULTI-THREADED SYSTEMS | 05-02-2013 |
20150100950 | METHOD AND APPARATUS FOR INSTRUCTION SCHEDULING USING SOFTWARE PIPELINING - A method for scheduling loop processing of a reconfigurable processor includes generating a dependence graph of instructions for the loop processing; mapping a first register file of the reconfigurable processor on an arrow indicating inter-iteration dependence on the dependence graph; and searching for schedules of the instructions based on the mapping result. | 04-09-2015 |
20160098257 | SYSTEMS AND METHODS FOR FOOTPRINT BASED SCHEDULING - A system can generate and impose constraints on a compiler/scheduler so as to specifically minimize the footprints of one or more program variables. The constraints can be based on scopes of the variables and/or on dependence distances between statements specifying operations that use the one or more program variables. | 04-07-2016 |