Search

Scratch enables children to learn about programming by creating games and animations, and is currently one of the most popular introductory programming languages. While Scratch has been found to increase students’ motivation and interest in programming, it has been debated whether Scratch users practice and learn about core programming concepts such as loops, conditional expressions, procedures and variables. This paper presents a large scale study of the progression of the programming concepts practiced by Scratch users through an analysis of their complete public project portfolios. A dataset of over 112 thousand authors and their 1 million projects was constructed and analyzed from three viewpoints. First, we investigate the development of programming concepts by looking at block usage statistics for each project in the users’ repositories. Second, we score and analyze the dataset using a computational thinking rubric. Third, we identify users that have left the Scratch platform and evaluate the learning goals they have achieved. Our results show that, while users progress in Scratch, there is a positive trend in the use of all concepts that were examined. Within the least utilized concepts, even after the 20th project of Scratch users, are procedures, conditional loops and logic operations. Examining the users who have left the Scratch platform after creating at least the mean amount of nine projects, we measured that half had left without ever utilizing procedures, and a third had left without ever utilizing conditional loops.

Acceleration is a technique for summarising loops by computing a closed-form representation of the loop behaviour. The closed form can be turned into an accelerator, which is a code snippet that skips over intermediate states of the loop to the end of the loop in a single step. Program analysers rely on invariant generation techniques to reason about loops. The state-of-the-art invariant generation techniques, in practice, often struggle to find concise loop invariants, and, instead, degrade into unrolling loops, which is ineffective for non-trivial programs. In this paper, we evaluate experimentally whether loop accelerators enable existing program analysis algorithm to discover loop invariants more reliably and more efficiently. This paper is the first comprehensive study on the synergies between acceleration and invariant generation. We report our experience with a collection of safe and unsafe programs drawn from the Software Verification Competition and the literature.

Data Level Parallelism has been improving performance-energy tradeoff of current processors by coupling SIMD engines, such as Intel AVX and ARM NEON. Special libraries and compilers are used to support DLP execution on such engines. However, timing overhead on hand coding is inevitable since most software developers are not skilled to extract DLP using unfamiliar libraries. In addition, DLP detection through compiler, besides breaking software compatibility, is limited to static code analysis, which compromises performance gains. In this work, we propose a runtime DLP detection named as Dynamic SIMD Assembler, which transparently identifies vectorizable code regions to execute in the ARM NEON engine. Due to its dynamic fashion, DSA keeps software compatibility and avoids timing overhead on software developing process. Results have shown that DSA outperforms ARM NEON auto-vectorization compiler by 32% since it covers wider vectorized regions, such as Dynamic Range, Sentinel and Conditional Loops. In addition, DSA outperforms hand-vectorized code using ARM library by 26% reducing 45% of energy consumption with no penalties over software development time.

The chapter introduces the concepts of counted ( for ) and conditional ( while ) loops. Many common uses such as summing and counting are covered using the programming method. Nested loops are also introduced. Some more sophisticated uses of loops such as error-checking and combining loops and selection statements are also covered. Finally, vectorizing code, by using built-in functions and operators on vectors and matrices instead of looping through them, is demonstrated. Tips for writing efficient code are emphasized, and tools for analyzing code are introduced.

Loops are a fundamental concept in computing and well known to be difficult for novices. Recent research shows that the open-ended learning approach often used in teaching block-based programming can be insufficient to help young students gain a solid understanding of computing concepts. Misconceptions about loop are very common despite the user-friendly block-based programming syntax. This study aims to contribute to the current understanding of how elementary-aged students can learn the concept of loops through a more structured instructional design. We engage students in structured learning activities consisting of "tangible" programming concept demo and progressive problem solving exercises. These activities were used to teach a group of 3-5th graders two types of loops: counting loops that repeat a set number of times without logic conditions, and conditional loops where the loop iteration is controlled by a Boolean condition. The evaluation results indicate that most students are able to understand and use counting loops correctly in their programs after the weeklong class. The understanding of conditional loops, however, remains difficult for elementary-aged students. Our study suggests that computing concepts may be learned more effectively with a structured instruction setting. Nonetheless, teaching young students conditional loops, especially how to apply them in computational problem solving is a very challenging task even in block-based environments.

International audience; Loop collapsing is a well-known loop transformation which combines some loops that are perfectly nested into one single loop. It allows to take advantage of the whole amount of parallelism exhibited by the collapsed loops, and provides a perfect load balancing of iterations among the parallel threads. However, in the current implementations of this loop optimization , as the ones of the OpenMP language, automatic loop collapsing is limited to loops with constant loop bounds that define rectangular iteration spaces, although load imbalance is a particularly crucial issue with non-rectangular loops. The OpenMP language addresses load balance mostly through dynamic runtime scheduling of the parallel threads. Nevertheless, this runtime schedule introduces some unavoidable execution-time overhead, while preventing to exploit the entire parallelism of all the parallel loops. In this paper, we propose a technique to automatically collapse any perfectly nested loops defining non-rectangular iteration spaces, whose bounds are linear functions of the loop iterators. Such spaces may be triangular, tetrahedral, trapezoidal, rhomboidal or parallelepiped. Our solution is based on original mathematical results addressing the inversion of a multi-variate polynomial that defines a ranking of the integer points contained in a convex polyhedron. We show on a set of non-rectangular loop nests that our technique allows to generate parallel OpenMP codes that outperform the original parallel loop nests, parallelized either by using options " static " or " dynamic " of the OpenMP-schedule clause.

This paper proposes a definition of non-ranking functions of loop programs and investigates how to apply the techniques on synthesize Non-ranking functions of loop programs. It is shown that this new non-ranking function works well to determine the termination of loop programs.

Ever since their introduction by Hoare in 1969, invariant assertions have, justifiably, played a key role in the analysis of while loops. In this paper, we discuss a distinct but related concept, viz invariant relations, and show how these can be used to answer many questions pertaining to the analysis of loops, including: how to compute the function of the loop; how to compute an invariant assertion of the loop; how to compute a weakest precondition of the loop; how to compute a strongest postcondition of the loop; how to compute the termination condition of a loop; how to verify whether the loop computes a given function; how to verify whether the loop is correct with respect to a given specification; and finally how to compute an invariant function for the loop. Using a tool we have developed at the University of Tunis to derive invariant relations, we show how all these tasks can be automated by means of a computer algebra system, viz Mathematica (©Wolfram Research). Whenever applicable, we compare the performance of our tool against the performance of others.

Using the notion of an elementary loop, Gebser and Schaub (2005. Proceedings of the Eighth International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR’05 ), 53–65) refined the theorem on loop formulas attributable to Lin and Zhao (2004) by considering loop formulas of elementary loops only. In this paper, we reformulate the definition of an elementary loop, extend it to disjunctive programs, and study several properties of elementary loops, including how maximal elementary loops are related to minimal unfounded sets. The results provide useful insights into the stable model semantics in terms of elementary loops. For a nondisjunctive program, using a graph-theoretic characterization of an elementary loop, we show that the problem of recognizing an elementary loop is tractable. On the other hand, we also show that the corresponding problem is coNP-complete for a disjunctive program. Based on the notion of an elementary loop, we present the class of Head-Elementary-loop-Free (HEF) programs, which strictly generalizes the class of Head-Cycle-Free (HCF) programs attributable to Ben-Eliyahu and Dechter (1994. Annals of Mathematics and Artificial Intelligence 12, 53–87). Like an HCF program, an HEF program can be turned into an equivalent nondisjunctive program in polynomial time by shifting head atoms into the body., Postprints der Universität Potsdam : Mathematisch-Naturwissenschaftliche Reihe, 566

The detection of informational and logical program step dependencies is a key problem when performing equivalent transformations. In this article we consider this problem for systems of loops which represent concentration of mass computations and are the biggest challenge in parallel execution. The prototype of program formalization is C language just because of it's popularity and it being an intermediate language for compilation of most programming languages including object-oriented ones. We present a shorter version of proof of existence of an algorithm for transforming any system of loops to separated form where data selection for processing is represented as a chain of procedures that select data at least for the immediately following procedures. Last procedure is called a loop kernel; other procedures are referred to as loop controllers. For such programs informational dependencies of loop iterations are determined by a system of natural number equations that connect loop controller functions and index expressions of array variables or array pointers. For the programs where these functions are linear, the solution of such systems is an algorithmically solvable problem. For more complex cases, for example when the functions are arbitrary polynomials, the problem is algorithmically unsolvable. This result points a way to construct programming languages with algorithmically detectable parallelism in the loop kernels. We introduce a notion of data fullness for program classes as ability to select array data elements with any algorithmic function. This characteristic is different from an algorithmic fullness for the classes-class may be full in one sense but not in another.

This paper introduces a new way to obtain the dynamical response of Euler–Bernoulli beams under large deflections. They are simulated with parsimonious models based on a two integrated neural networks. Our article proves that neural network based-reduced modelling allows mechanical simulations to benefit shorter time processing without a great loss of accuracy. Our model reduction technique ensures a good error-speed compromise. It rapidly leads to algebraic generic model matching interactive simulation or high-realistic multi-sensorial virtual protoyping requirements. The originality of our solution consists in the linking of two neural networks. They are integrated in a conditional loop. First, the article presents a systematic numerical technique that enables users to efficiently build an optimal neural network. This approach is based on the handling of discrete optimization evolutionary technique. Our optimization process is applied to the construction of the two neural networks. From an exhaustive learning base created from non-linear finite element analysis series, we secondly clearly describe our two neural network-based reduced models. The first neural network that enables nodal displacements to be determined from boundary conditions is linked to the second one that aims to set boundary conditions from a deformation state. The new relationship is finally analysed for justifying the successes of our proposal. The article completely details a new numerical process supervising the making of an integrated neural network loop being a new from of model for beam non-linear behaviour representation.

Computation intensive tasks which consist of nested short loops usually suffer from massive control overhead, or memory size increasing when employing loop unrolling. In this approach, by introducing a modified instruction fetch unit with instruction FIFO and multiple loop controllers, loops can be performed in hardware, and single execution-cycle instructions can be executed in self-loop. Therefore no loop overhead exists for the optimized processor. The flexibility and the instruction granularity are maintained. Special domains for loop and repeat indications are added in the application-specific instructions. The proposed approach achieves dramatically performance and area benefits for many nested short loop dominated programs where the loops are determinable.

International audience; Loop transformations are known to be important for performance of compute-intensive programs, and are often used to expose parallelism. However, many transformations involving loops often obfuscate the code, and are cumbersome to apply by hand. The goal of this paper is to explore alternative methods for expressing parallelism that are more friendly to the programmer. In particular, we seek to expose parallelism without significantly changing the original loop structure. We illustrate how clocks in X10 can be used to express some of the traditional loop transformations, in the presence of parallelism, in a manner that we believe to be less invasive. Specifically, expressing parallelism corresponding to one-dimensional affine schedules can be achieved without modifying the original loop structure and/or statements.

The theorem on loop formulas due to Fangzhen Lin and Yuting Zhao shows how to turn a logic program into a propositional formula that describes the program's stable models. In this paper we simplify and generalize the statement of this theorem. The simplification is achieved by modifying the definition of a loop in such a way that a program is turned into the corresponding propositional formula by adding loop formulas directly to the conjunction of its rules, without the intermediate step of forming the program's completion. The generalization makes the idea of a loop formula applicable to stable models in the sense of a very general definition that covers disjunctive programs, programs with nested expressions, and more.

A loop is a critical part of any program. A loop is normally executed a large number of times, hence if any statement can be moved outside the loop then computation can speed-up. Loop invariant computations have been studied in great detail [1, 2]. Here a computation, which does not change inside the loop (on successive execution of the loop), is done before the loop. Such a computation involves only the loop invariant variables. These are variables, whose value does not change inside the loop.Here we talk about a variable, which changes inside the loop, but only the last value is useful. The computation needed in the definition of this variable can be moved outside the loop (after the loop).Formally a loop-dead variable is that which is defined in the loop but not used in the loop. Later we extend this definition as follows: A loop-dead variable is that which is not used inside the loop except in the definition of the other loop dead variables.

Two restricted imperative programming languages are considered: One is a slight modification of a loop language studied intensively in the literature, the other is a stack programming language over an arbitrary but fixed alphabet, supporting a suitable loop concept over stacks. The paper presents a purely syntactical method for analysing the impact of nesting loops on the running time. This gives rise to a uniform measure μ on both loop and stack programs, that is, a function that assigns to each such program P a natural number μ(P) computable from the syntax of P.It is shown that stack programs of μ-measure n compute exactly those functions computed by a Turing machine whose running time lies in Grzegorczyk class En+2. In particular, stack programs of μ-measure 0 compute precisely the polynomial-time computable functions.Furthermore, it is shown that loop programs of μ-measure n compute exactly the functions in En+2. In particular, loop programs of μ-measure 0 compute precisely the linear-space computable functions.

Loops in programs are the source of many optimizations for improving program performance, particularly on modern high-performance architectures as well as vector and multithreaded systems. Techniques such as loop invariant code motion, loop unrolling and loop peeling have demonstrated their utility in compiler optimizations. However, many of these techniques can only be used in very limited cases when the loops are "well-structured" and easy to analyze. For instance, loop invariant code motion works only when invariant code is inside loops; loop unrolling and loop peeling work effectively when the array references are either constants or affine functions of index variable. It is our contention that there are many opportunities overlooked by limiting the optimizations to "well structured" loops. In many cases, even "badly-structured" loops may be transformed into "well structured" loops. As a case in point, we show how some loop-dependent code can be transformed into loop-independent code by transforming the loops. Our technique described in this paper relies on unfolding the loop for several initial iterations such that more opportunities may be exposed for many other existing compiler optimization techniques such as loop invariant code motion, loop peeling, loop unrolling and so on.

We present abstract acceleration techniques for computing loop invariants for numerical programs with linear assignments and conditionals. Whereas abstract interpretation techniques typically over-approximate the set of reachable states iteratively, abstract acceleration captures the effect of the loop with a single, non-iterative transfer function applied to the initial states at the loop head. In contrast to previous acceleration techniques, our approach applies to any linear loop without restrictions. Its novelty lies in the use of the Jordan normal form decomposition of the loop body to derive symbolic expressions for the entries of the matrix modeling the effect of n>=0 iterations of the loop. The entries of such a matrix depend on $n$ through complex polynomial, exponential and trigonometric functions. Therefore, we introduces an abstract domain for matrices that captures the linear inequality relations between these complex expressions. This results in an abstract matrix for describing the fixpoint semantics of the loop. Our approach integrates smoothly into standard abstract interpreters and can handle programs with nested loops and loops containing conditional branches. We evaluate it over small but complex loops that are commonly found in control software, comparing it with other tools for computing linear loop invariants. The loops in our benchmarks typically exhibit polynomial, exponential and oscillatory behaviors that present challenges to existing approaches. Our approach finds non-trivial invariants to prove useful bounds on the values of variables for such loops, clearly outperforming the existing approaches in terms of precision while exhibiting good performance., Extended version with appendices of paper accepted to POPL'2014

Loop checking mechanisms are used to detect and prune infinite SLD derivations, through run time checks which are introduced in logic program interpreters. Simple loop checks, i.e. checks which do not depend on the specific logic program, have been widely studied in literature. Since no sound and complete loop check exists even in the case of function-free programs, several subclasses have been characterized for which sound and complete loop checks can be determined. In this paper a theoretical framework for analysing properties of loop check mechanisms for logic programs is proposed, which exploits general mathematical results about well-quasi-ordered ( wqo ) sets. In a way, the method can be viewed as a counterpart of well known techniques based on well-founded partial-ordering, used in termination proofs for rewriting systems and for logic programs. The main results are obtained on the basis of a combinatorial analysis of properties of wqo sets of goals. As shown in the paper, subclasses of programs, for which sound and complete simple loop checks exist, can be easily framed in the wqo approach. Reasons for the different behaviours of subsumption loop checks based on list and multiset goal comparisons are also plainly highlighted.

A kind of loop function LoopN in Genetic Programming (GP) is proposed. Different from other forms of loop function, such as While-Do and Repeat-Until, LoopN takes only one argument as its loop body and makes its loop body simply runN times, so infinite loops will never happen. The problem of how to avoid too many layers of loops in Genetic Programming is also solved. The advantage of LoopN in GP is shown by the computational results in solving the mower problem.

This paper presents a programmable many-core platform containing 64 cores routed in a hierarchical network for biomedical signal processing applications. Individual core processors are based on a RISC architecture with DSP enhancement blocks. Given the number of conditional program loops in DSP applications such as FFT, additional hardware blocks are added that operate in parallel to each core processor. The two blocks calculate the FFT input addresses and determine if a conditional loop is necessary. Performing these operations in parallel to the main processor greatly reduces the time to completion for a DSP application. Each processor is implemented in 65 nm CMOS using standard cell libraries. The 64-core platform occupies 19.51 mm2 and runs at 1.18 GHz at 1 V. For demonstration, Electroencephalogram (EEG) seizure detection and analysis and ultrasound spectral doppler are mapped onto the cores. The seizure detection and analysis algorithm utilizes 60 processors and takes 890 ns to execute. Spectral doppler utilizes 29 processors and takes 715 ns to run.

This chapter goes over the a few concepts that enable the LaunchPad to make decisions. Conditionals branches (if, else, switch) and conditional loops (while, for) are introduced. The logical concepts are used in Project 3 to reflect the operation flow of the LaunchPad.

Considering a dynamic conditional loop ℒ, i.e. involving an if—then—else with a dynamic condition, our aim is to restructure ℒ in order to extract the inherent parallelism. Assuming the dependence distances (DD) carried by ℒ to be non-constant, we first study their corresponding signs. This leads to splitting the loop index set into at most four subsets where each DD has a constant sign. According to the respective signs of the DDs, ℒ is consequently split into a series of loops that may be sequential, parallel or partially parallel. The practical efficiency of our approach is analysed through simulation experiments run on two vector-multiprocessors: a Stardent 3000 (2 CPUs) and a CRAY Y-MP (4 CPUs).

Let L be a static conditional loop (SCL), i.e. involving an IF-THEN-ELSE statement with a static condition, that carries dependences with non-constant distances. We address the problem of restructuring L in order to extract the inherent parallelism. Adopting a dependence analysis approach, the restructuring procedure is essentially based on the study of the signs of the dependence distances. This leads to split the loop index set and consequently L into a series of successive (IF-THEN-ELSE and/or IF-THEN) SCLs. Each new loop is associated to a subset of the index set, carries a constant sign dependence distance and may be sequential, parallel or partially parallel. The practical efficiency of the approach is analysed through performance evaluation experiments run on a Stardent 3000 vector-biprocessor.

Loop leaping is the colloquial name given to a form of program analysis in which summaries are derived for nested loops starting from the innermost loop and proceeding in a bottom-up fashion considering one more loop at a time. Loop leaping contrasts with classical approaches to finding loop invariants that are iterative; loop leaping is compositional requiring each stratum in the nest of loops to be considered exactly once. The approach is attractive in predicate abstraction where disjunctive domains are increasingly used that present long ascending chains. This paper proposes a simple and an efficient approach for loop leaping for these domains based on viewing loops as closure operators.

A simple linear loop is a simple while loop with linear assignments and linear loop guards. If a simple linear loop has only two program variables, we give a complete algorithm for computing the set of all the inputs on which the loop does not terminate. For the case of more program variables, we show that the non-termination set cannot be described by Tarski formulae in general.

Barrier MIMD's are asynchronous multiple instruction stream, multiple data stream architectures capable of parallel execution of variable execution time instructions and arbitrary control flow (e.g., while loops and calls); however, they differ from conventional MIMD's in that the need for run-time synchronization is significantly reduced. The authors consider the problem of scheduling nested loop structures on a barrier MIMD. The basic approach employs loop coalescing, a technique for transforming a multiply-nested loop into a single loop. Loop coalescing is extended to nested triangular loops, in which inner loop bounds are functions of outer loop indices. In addition, a more efficient scheme to generate the original loop indices from the coalesced index is proposed for the case of constant loop bounds. These results are general, and can be applied to extend previous work using loop coalescing techniques. The authors concentrate on using loop coalescing for scheduling barrier MIMDs, and show how previous work in loop transformations and linear scheduling theory can be applied to this problem. >

Loop constructs play an important role in obtaining speed-up in parallel programming. In this paper, we explain the solutions applied for optimizing loops in parallel programs in terms of three patterns for parallel programming. These patterns can be used for parallel programming by users who have medium background on parallel programming and compiler courses. They can also be implemented in the compilers as a part of program optimization process.

Many loop nests in scientific codes contain a parallelizable outer loop but have an inner loop for which the number of iterations varies between different iterations of the outer loop. When running this kind of loop nest on a SIMD machine, the SIMD-inherent restriction to single program counter common to all processors will cause a performance degradation relative to comparable MIMD implementations. This problem is not due to limited parallelism or bad load balance, it is merely a problem of control flow. This paper presents a loop transformation, which we call loop flattening , that overcomes this limitation by letting each processor advance to the next loop iteration containing useful computation, if there is such an iteration for the given processor. We study a concrete example derived from a molecular dynamics code and compare performance results for flattened and unflattened versions of this kernel on two SIMD machines, the CM-2 and the DECmpp 12000. We then evaluate loop flattening from the compiler's perspective in terms of applicability, cost, profitability, and safety. We conclude with arguing that loop flattening, whether performed by the programmer or by the compiler, introduces negligible overhead and can significantly improve the performance of scientific codes for solving irregular problems.

We extend Meyer and Ritchie's Loop language with higher-order procedures and procedural variables and we show that the resulting programming language (called Loop ω ) is a natural imperative counterpart of Gödel System T. The argument is two-fold: (1) we define a translation of the Loop ω language into System T and we prove that this translation actually provides a lock-step simulation, (2) using a converse translation, we show that Loop ω is expressive enough to encode any term of System T. Moreover, we define the “iteration rank” of a Loop ω program, which corresponds to the classical notion of “recursion rank” in System T, and we show that both translations preserve ranks. Two applications of these results in the area of implicit complexity are described.

SUMMARY The purpose of this paper is to present a method for testing computer programs with iteration loops. Given such programs, we have shown that for classes of program paths, identified as sequences of simple loop paths, there is a characterizing function called a simple loop pattern. The key idea of simple loop patterns is that these special functions form a base set which can represent any path computation in the given program. A software tool called SILOP has been developed to automatically generate these simple loop patterns, and each corresponding sequence of simple loop paths can be considered as a test case. The tester uses each test case, and with knowledge of the application program, can generate corresponding test data. This paper also presents a method for selecting the specific paths and test data to determine the simple loop pattern reliably. The tester can use this selection method to predict the number of tests required. In order to apply this selection method, the given program must be a linear computer program. The SILOP tool and this test selection method have been applied to commercial software; in this paper, this computational experience is reported and several examples are given to demonstrate the approach.

Proving termination of program loops is necessary in many applications, especially those safety critical software. Discovering ranking function is a classical method to prove the termination, but the existence of ranking function is a sufficient condition on the termination of a loop program. In this paper, we present an algorithm to remedy the limitation of ranking function for analyzing the termination of linear programs with conditionals. We transform the linear loop programs with conditionals into the nested linear loop programs, and then check whether the inner loop terminates or not by positive eigenvalues and their corresponding eigenvectors. If one of the inner loop in the nested linear loop is nonterminating, then the linear loop is nonterminating. Otherwise, we use discovering ranking functions based on qualifier elimination to analyze the termination of the linear loop. To illustrate the main idea of the algorithm, we perform it on some examples.

Non-termination analysis of loop programs plays a central role in many applications, especially in the field of safety critical softwares. This paper presents a method to analyze non-termination of linear programs with conditionals. We transform the linear loop programs with conditionals into the nested linear loop programs, and then check whether the inner loop terminates or not by the positive eigenvalues and their corresponding eigenvectors. If one of the inner loop in the nested linear loop is non-terminating, then the linear loop is non-terminating. Otherwise, we need to use ranking function or finite differences of expressions over transition systems to analyze the termination of the outer loop.

We present a novel loop transformation technique, particularly well suited for optimizing embedded compilers, where an increase in compilation time is acceptable in exchange for significant performance increase. The transformation technique optimizes loops containing nested conditional blocks. Specifically, the transformation takes advantage of the fact that the Boolean value of the conditional expression, determining the true/false paths, can be statically analyzed using a novel interval analysis technique that can evaluate conditional expressions in the general polynomial form. Results from interval analysis combined with loop dependency information is used to partition the iteration space of the nested loop. In such cases, the loop nest is decomposed such as to eliminate the conditional test, thus substantially reducing the execution time. Our technique completely eliminates the conditional from the loops (unlike previous techniques) thus further facilitating the application of other optimizations and improving the overall speedup. Applying the proposed transformation technique on loop kernels taken from Mediabench, SPEC-2000, mpeg4, qsdpcm and gimp, on average we measured a 175% (1.75X) improvement of execution time when running on a SPARC processor, a 336% (4.36X) improvement of execution time when running on an Intel Core Duo processor and a 198.9% (2.98X) improvement of execution time when running on a PowerPC G5 processor.

Knowing the boundaries of loops is an important prerequisite for both, static and dynamic worst case execution time (WCET) analysis. However, loop bound calculation is a complex task of its own, and often more effort than planned has to be put into it. This paper describes a simple and quick method for loop bound calculation using a model checker that cannot only find loop bounds for integer iterator variables but works with practically all kind of loops.

For some sequential loops, existing techniques that form speculative threads only at their loop boundaries do not adequately expose the speculative parallelism inherent in them. This is because some inter-iteration dependences, which translate into inter-thread dependences at run time, are too costly to synchronize or speculate. This paper presents a novel compiler technique, called loop recreation, to transform a loop into a prologue, a kernel loop - formed with instructions from two adjacent iterations, and an epilogue so that the inter-iteration dependences in the kernel are less costly to enforce at run time than those in the original loop. We prove the concept by giving an algorithm for finding an optimal loop recreation with respect to a simple misspeculation cost model and by demonstrating performance advantages of loop recreation over two recent techniques for speculative multi-core systems running four irregular applications with indirect array accesses.

Writing loops with tail-recursive function calls is the equivalent of writing them with goto's. Given that loop packages for Lisp-family languages have been around for over 20 years, it is striking that none have had much success in the Scheme world. I suggest the reason is that Scheme forces us to be precise about the scoping of the various variables introduced by our loop forms, something previous attempts to design ambitious loop forms have not managed to do.I present the design of a loop package for Scheme with a well-defined and natural scoping rule, based on a notion of control dominance that generalizes the standard lexical-scope rule of the λ-calculus. The new construct is powerful, clear, modular and extensible.The loop language is defined in terms of an underlying language for expressing control-flow graphs. This language itself has interesting properties as an intermediate representation.

The actual behaviour of a hardware device available for an implementation of a control system can be simulated by a program, allowing the hardware device to be proved correct by standard software techniques. In this paper we formalise event semantics of hardware description language in the form of relations and use relation calculus to prove properties (including termination, stability, and uniqueness of final state) of combinational programs, the cycle behaviour of which is defined as a conditional loop of non-deterministic choices between generalised parallel assignments.

We present a systematic analysis how one can improve performance of probabilistic programmable quantum processors. We generalize a simple Vidal-Masanes-Cirac processor that realizes U(1) rotations on a qubit with the phase of the rotation encoded in a state of the program register. We show how the probability of success of the probabilistic processor can be enhanced by using the processor in loops. In addition we show that the same strategy can be utilized for a probabilistic implementation of non-unitary transformations on qubits. In addtion, we show that an arbitrary SU(2) transformations of qubits can be encoded in program state of a universal programmable probabilistic quantum processor. The probability of success of this processor can be enhanced by a systematic correction of errors via conditional loops. Finally, we show that all our results can be generalized also for qudits. In particular, we show how to implement SU (N) rotations of qudits via programmable quantum processor and how the performance of the processor can be enhanced when it is used in loops., Comment: 8 pages, 0 figures

On parallel computers, parallelism and locality are critical points for the performance of programs. It is known that locality and parallelism of loop nests can be improved by loop transformations. However, many useful loop transformations are restricted to perfectly nested loop nests. We present a loop-synthesizing transformation for maintaining parallelism and improving locality, with respect to a sequence of parallel loop nests. Since the result of our synthesizing transformation is a perfectly nested loop nest, we can directly perform the loop transformations which are restricted to perfectly nested loop nests, to further parallelize and to further enhance locality after the transformation.

Loops in programs are the source of many optimizations leading to performance improvements, particularly on modern high-performance architectures as well as vector and multithreaded systems. Among the optimization techniques, loop peeling is an important technique that can be used to parallelize computations. The technique relies on moving computations in early iterations out of the loop body such that the remaining iterations can be executed in parallel. A key issue in applying loop peeling is the number of iterations that must be peeled off from the loop body. Current techniques use heuristics or ad hoc techniques to peel a fixed number of iterations or a speculated number of iterations. To our knowledge, no formal or systematic technique that can be used by compilers to determine the number of iterations that must be peeled off based on the program characteristics. In this paper we introduce one technique that uses variable dependence analysis for identifying the number of iterations to be peeled off. Our goal is to find general techniques that can accurately determine the ideal number of iterations for loop peeling, while working within the context of other loop optimizations including code motion.

One of the serious limitations of domain testing is the potentially infinite number of domains to be examined in the presence of iteration loops in the computer program. The authors show that only a small number of domain needs to be examined, and that one can concentrate on testing certain borders of those domains. It is first shown that for definite loops, where the number of iterations is known on entry, iteration loops can be represented by a primitive recursive schema. This involves the identification of simple loop patterns, and it is proved that these simple loop patterns can be used as basic building blocks to form arbitrarily complex loop patterns. It is further shown that domain testing can be adapted to test these simple loop patterns, precluding the necessity of testing any of the complex patterns. A bound is obtained on the number of loop patterns that have to be tested and worst cases identified for the corresponding control-flow graphs. >

Loops in programs are the source of many optimizations for improving program performance, particularly on modern high-performance architectures as well as vector and multithreaded systems. Techniques such as loop invariant code motion, loop unrolling and loop peeling have demonstrated their utility in compiler optimizations. However, many of these techniques can only be used in very limited cases when the loops are ”well-structured” and easy to analyze. For instance, loop invariant code motion works only when invariant code is inside loops; loop unrolling and loop peeling work effectively when the array references are either constants or affine functions of index variable. It is our contention that there are many opportunities overlooked by limiting the optimizations to well structured loops. In many cases, even ”badly-structured” loops may be transformed into well structured loops. As a case in point, we show how some loop-dependent code can be transformed into loop-invariant code by transforming the loops. Our technique described in this paper relies on unfolding the loop for several initial iterations such that more opportunities may be exposed for many other existing compiler optimization techniques such as loop invariant code motion, loop peeling, loop unrolling, and so on.

In the case of imperfect loop nests, some researchers suggested to first use Abu-Sufah's Non-Basic-to-Basic-Loop transformation to convert them into perfect loop nests and then apply the unimodular transformation approach. This paper identifies some limitations of this approach, describes some improvements, and provides some insights into the problem of restructuring imperfect loop nests.

Loop transformation is a crucial step in parallelizing compilers. We introduce the concept of positive coordinate basis for deriving loop transformations. The basis serves to find proper loop transformations to change the dependence vectors into the desired forms. We demonstrate how this approach can, systematically extract maximal outer loop parallelism. Based on the concept, we can also construct a minimal set of synchronization vectors, which are deadlock free, to transform the inner serial loops into doacross loops.

Optimization of hardware resources for conditional data-flow graph behavior is particularly important when conditional behavior occurs in cyclic loops and maximization of throughput is desired. In this paper, an exact and efficient conditional resource sharing analysis using a guardbased control representation is presented. The analysis is transparent to a scheduler implementation. The proposed technique systematically handles complex conditional resource sharing for cases when folded (software pipelined) loops include conditional behavior within the loop body.

We concentrate on three fundamental phases, data dependence testing, parallel loop transformation, and parallel loop scheduling, for loop parallelization in parallelizing compilers, running on multiprocessor systems. A new model of exploiting loop parallelization by using knowledge-based techniques is first proposed. The knowledge-based approach integrates existing data dependence tests, loop transformations and loop schedules, to make good use of their abilities for extracting more parallelism. Three rule-based systems, called the K-Test, IPLS and KPLT, are then developed by repertory grid analysis and an attribute ordering table to construct the knowledge base, respectively. These systems can choose an appropriate test, transform and schedule, then apply the resulting methods to perform loop parallelization and gain a high speedup rate. For example, the KPLT can choose the appropriate loop transformations to reorder the execution of statements and loop iterations for parallelization. Unlike the previous researches that must use the one-pass approach, we introduce the idea of multipass which may explore more parallelism of loops. Experimental results show that our new model can achieve higher speedup on parallelizing compilers. Furthermore, for system maintenance and extensibility, our approach is obviously superior to others.

By analyzing the features such as asynchronism, concurrency and event-driven control of the autonomous underwater vehicle (AUV) system, the concepts of basic procedure, concurrent procedure and parallel procedure are proposed. In addition, the authors define operators such as sequence, loop, selection, condition, conditional loop, parallel, synchronous concurrency and concurrent communication, whose Petri net representations are also given. Accordingly, the authors propose a novel modeling method of the AUV based on Petri net. On the basis of the above work, the broadcasting module, perceptional module, planing module and control module are constructed using a bottom-up approach. Finally, a synchronous model is developed and an analysis of the model of the AUV system is given.

A new method of parallel loop execution is presented. Firstly, all the loop iterations are executed in parallel. Then, the ends of pairs of dependent iterations are re-executed. The method requires no conversion of a source loop into an equivalent serial-parallel loop, involving iteration indices to be converted into new ones, that appears to be a typical requirement in the most known loop paralleling approaches such as unimodular and nonunimodular linear transformation methods. Possibilities of serial and parallel correction processes are discussed. Experimental results are considered. As follows from experiments, applying the method can be reasonable for the loops with a small fraction of dependent iterations.