Search

With the advancement of the automotive industry, a need for developing and maintaining in-car embedded software has risen. In-car embedded systems are limited with the number of available resources including random access memory. In this paper, the goal was to reduce the RAM consumption of automatically generated tests for the embedded computer systems based on the Infineon Tricore AURIX microcontroller. The program that was optimized was written in C, and the code itself was generated using the proprietary Python tools. There are various techniques used for reducing the RAM footprint. In this paper we used loop inversion, loop unrolling, data type size reduction, memory alignment and heuristic methods. Also, compiler optimization options were used but not tested on the board. We achieved up to 10.97% lower RAM footprint with the optimized program code successfully passing all the initial tests.

With increasing demands for performance by embedded systems, especially by digital signal processing (DSP) applications, embedded processors must increase available instruction-level parallelism (ILP) within significant constraints on power consumption and chip cost. Unfortunately, supporting a large amount of ILP on a processor while maintaining a single register file increases chip cost and potentially decreases overall performance due to increased cycle time. To address this problem, some modern embedded processors partition the register file into multiple low-ported register files, each directly connected with one or more functional units. These functional unit/register file groups are called clusters. Clustered VLIW (very long instruction word) architectures need extra copy operations or delays to transfer values among clusters. To take advantage of clustered architectures, the compiler must expose parallelism for maximal functional-unit utilization, and schedule instructions to reduce intercluster communication overhead. High-level loop transformations offer an excellent opportunity to enhance the abilities of low-level optimizers to generate code for clustered architectures. This dissertation investigates the effects of three loop transformations, i.e., loop fusion, loop unrolling, and unroll-and-jam, on clustered VLIW architectures. The objective is to achieve high performance with low communication overhead. This dissertation discusses the following techniques: (1) Loop fusion. This research examines the impact of loop fusion on clustered architectures. A metric based upon communication costs for guiding loop fusion is developed and tested on DSP benchmarks. (2) Unroll-and-jam and loop unrolling. A new method that integrates a communication cost model with an integer-optimization problem is developed to determine unroll amounts for loop unrolling and unroll-and-jam automatically for a specific loop on a specific architecture. These techniques have been implemented and tested using DSP benchmarks on simulated, clustered VLIW architectures and a real clustered, embedded processor, the TI TMS320C64X. The results show that the new techniques achieve an average speedup of 1.72–1.89 on five different clustered architectures.

Modern high-level synthesis (HLS) tools commonly employ pipelining to achieve efficient loop acceleration by overlapping the execution of successive loop iterations. While existing HLS pipelining techniques obtain good performance with low complexity for regular loop nests, they provide inadequate support for effectively synthesizing irregular loop nests. For loop nests with dynamic-bound inner loops, current pipelining techniques require unrolling of the inner loops, which is either very expensive in resource or even inapplicable due to dynamic loop bounds. To address this major limitation, this paper proposes ElasticFlow, a novel architecture capable of dynamically distributing inner loops to an array of processing units (LPUs) in an area-efficient manner. The proposed LPUs can be either specialized to execute an individual inner loop or shared among multiple inner loops to balance the tradeoff between performance and area. A customized banked memory architecture is proposed to coordinate memory accesses among different LPUs to maximize memory bandwidth without significantly increasing memory footprint. We evaluate ElasticFlow using a variety of real-life applications and demonstrate significant performance improvements over a state-of-the-art commercial HLS tool for Xilinx FPGAs.

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.

In the wake of the current trend of increasing the number of cores on a chip, compiler optimizations for improving the memory performance have assumed increased importance. Loop fusion is one such key optimization that can alleviate memory and bandwidth wall and thus improve parallel performance. However, we find that loop fusion in interesting memory-intensive applications is prevented by the existence of dependences between temporary variables that appear in different loop nests. Furthermore, known techniques of allowing useful transformations in the presence of temporary variables, such as privatization and expansion, prove insufficient in such cases. In this work, we introduce variable liberalization , a technique that selectively removes dependences on temporary variables in different loop nests to achieve loop fusion while preserving the semantical correctness of the optimized program. This removal of extra-stringent dependences effectively amounts to variable expansion, thus achieving the benefit of an increased degree of freedom for program transformation but without an actual expansion. Hence, there is no corresponding increase in the memory footprint incurred. We implement liberalization in the Pluto polyhedral compiler and evaluate its performance on nine hot regions in five real applications. Results demonstrate parallel performance improvement of 1.92 × over the Intel compiler, averaged over the nine hot regions, and an overall improvement of as much as 2.17 × for an entire application, on an eight-core Intel Xeon processor.

Nested loops represent a significant portion of application runtime in multimedia and DSP applications, an important domain of applications for coarse-grained reconfigurable architectures (CGRAs). While conventional approaches to mapping nested loops utilize only a single-dimensional pipelining, which is either along the innermost loop or along an outer loop, in this paper, we explore an orthogonal approach of pipelining along multiple loop dimensions by first flattening the loop nest. To remedy the inevitable problem of repetitive outer-loop computation in flattened loops, we present a small set of special operations that can effectively reduce the number and frequency of micro-operations in the pipelined loop. We also present a loop transformation technique that can make our special operations applicable to a broader range of loops, including those with triangular iteration spaces. Our experimental results using imperfect loops from StreamIt benchmarks demonstrate that our special operations can cover a large portion of operations in flattened loops, improve performance of nested loops by nearly 30% over using loop flattening only, and achieve near-ideal executions on CGRAs for imperfect loops.

In digital communication systems, typical methodologies in determining loop parameters of the digital phase-locked loop (DPLL) are based on the mapping transformation from the analog domain to the digital domain. However, such transform based algorithms are relatively complicated and not straightforward, and they also cause the problem that loop parameters are affected by the pre-detection integration time greatly. To solve these issues, an effective direct method of determining loop parameters of the second-order DPLL in the z-domain is proposed in this paper. Through ascertaining specific positions of the closed-loop system function's poles inside the right-hand side of the z-plane's unit circle, unknown parameters are calculated directly and flexibly in this method, which enables the DPLL to acquire good low-pass filtering characteristic and system stability. This novel method not only reduces the complexity of solving the parameters, but also eliminates the effect of the pre-detection integration time on loop parameters. Simulation results are provided to confirm the feasibility of the proposed method and to show that the DPLL obtained by this method achieves the similar tracking performance to the discretized PLL.

Coarse-grained reconfigurable architecture (CGRA) is a promising architecture with high performance, high power efficiency, and attraction of flexibility. The computation-intensive portions of applications, i.e., loops, are often implemented on CGRAs for acceleration. The loop pipelining techniques are usually used to exploit the parallelism of loops. However, for nested loops, the existing loop pipelining methods often result in poor hardware utilization and low execution performance. To tackle this problem, this paper makes three contributions: 1) we propose the use of affine transformation to facilitate nested loop pipelining; 2) based on polyhedral model, we present a precise and general formulation of the nested loop pipelining problem on a CGRA; and 3) using the insights from problem formulation, we design a joint affine transformation and multipipeline merging approach to improve the performance of nested loop on CGRA. The experimental results show that our approach can improve the performance of nested loops up to 35% on average, compared with the state-of-the-art techniques.

This paper presents a loop gain optimization technique for integer- $N$ digital phase-locked loops with a time-to-digital converter. Due to noise filtering properties, a phase-locked loop has an optimal loop gain which gives rise to the best jitter performance, taking into account external and internal noise sources. By using the loop gain optimization technique, the digital phase-locked loops can automatically attain this loop gain in background to minimize the jitter. Theoretical analysis is presented. The stability issue and the impact of loop latency are also discussed. Finally, the analysis is compared to behavioral simulations with good agreement.

A modified code tracking loop for tracking the pseudo-random noise code in direct sequence spread spectrum signal is proposed. The modified loop differs from the typical through imposing a dual structure which incorporates a coarse loop with large loop parameters and an accurate loop with small loop parameters. The expression of the convergence time for the second-order delay-locked loop (DLL) is derived to measure the time of the convergence process. Two concepts, accuracy improvement and time improvement are defined to exhibit the performance enhancement of the modified loop. Simulation results show that the proposed method can realize a better trade-off between tracking accuracy and convergence time in the whole simulated carrier-to-noise ratio range. Also, the robustness of the modified loop is verified through eliminating the second convergence process which is regarded as the worst issue in the parameter-switching DLL.

International audience; Loop transformations such as tiling, parallelization or vector-ization are essential tools in the quest for high-performance program execution. But precise data dependence analysis is required to determine the validity of a loop transformation, and whether the compiler can apply it or not. In particular , current static analyses typically fail to provide precise enough dependence information when the code contains indirect memory accesses or even polynomial subscript functions to index arrays. This leads to considering superfluous may-dependences between instructions, in turn preventing many loop transformations to be applied. In this work we present a new framework to overcome several limitations of static dependence analyses, to enable aggressive loop transformations on programs with may-dependences. We statically generate a test to be evaluated at runtime which uses data dependence information to determine whether a program transformation is valid, and if so triggers the execution of the transformed code, falling back to the original code otherwise. These tests, originally constructed as a loop-based code with O(n 2d) iterations (d being the maximal loop depth of the program, n being the loop trip count), are reduced to a loop-free test of O(1) complexity thanks to a new quantifier elimination scheme that we introduce in this paper. The precision and low overhead of our method is demonstrated over 25 kernels containing may-alias memory pointers and polynomial memory access subscripts.

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.

Aiming at unbalanced three-phase power grid voltage, traditional phase locked loop was not able to restrain the negative sequence component in unbalanced grid voltage, which led to the poor accuracy of phase. Based on the traditional three-phase software phase locked loop model, the paper proposed a design of differential decoupling phase-locked loop. Through differential decoupling algorithm, the positive sequence component could be extracted from the unbalanced voltage. By this way, the ability of three phase software phase locked loop to resist unbalanced voltage had been improved. In Matlab, the improved software phase-locked loop was simulated. Compared with the traditional phase locked loop, the differential decoupling phase-locked loop was not only able to track the phase of grid voltage unbalance accurately without delay, but had excellent dynamic phase tracking performance.

Thread-level speculation becomes more attractive for the exploitation of thread-level parallelism from irregular sequential applications. But it is common for speculative threads to fail to reach the expected parallel performance. The reason is that the performance of speculative threads is extremely complicated by the fact that it not only suffers from the imprecision of compiler-directed performance estimation due to ambiguous control and data dependences, but also depends on the underlying hardware configuration and program behaviors. Thus, this paper proposes a statically greedy and dynamically adaptive approach for loop-level speculation to dynamically determine the best loop level at runtime. It relies on the compiler to select and optimize all loop candidates greedily, which are then proceeded on the cost-benefit analysis of different loop nesting levels for the determination of the order of loop speculation. Under the runtime loop execution prediction, we dynamically schedule and update the order of loop speculation, and ensure the best loop level to be always parallelized. Two different policies are also examined to maximize overall performance. Compared with traditional static loop selection techniques, our approach can achieve comparable or better performance.

In this paper, we present a solution to the problem of joint tiling and scheduling a given loop nest with uniform data dependencies symbolically. This challenge arises when the size and number of available processors for parallel loop execution is not known at compile time. But still, in order to avoid any overhead of dynamic (run-time) recompilation, a schedule of loop iterations shall be computed and optimized statically. In this paper, it will be shown that it is possible to derive parameterized latency-optimal schedules statically by proposing a two step approach: First, the iteration space of a loop program is tiled symbolically into orthotopes of parametrized extensions. Subsequently, the resulting tiled program is also scheduled symbolically, resulting in a set of latency-optimal parameterized schedule candidates. At run time, once the size of the processor array becomes known, simple comparisons of latency-determining expressions finally steer which of these schedules will be dynamically selected and the corresponding program configuration executed on the resulting processor array so to avoid any further run-time optimization or expensive recompilation. Our theory of symbolic loop parallelization is applied to a number of loop programs from the domains of signal processing and linear algebra. Finally, as a proof of concept, we demonstrate our proposed methodology for a massively parallel processor array architecture called tightly coupled processor array (TCPA) on which applications may dynamically claim regions of processors in the context of invasive computing.

Whereas three-phase phase locked loop could not get accurate phase position under three-phase unbalanced condition of the power grid, the design of single phase locked loop is implemented in the principle of single phase locked loop, based on FPGA technology. the paper explains design difficulties of single phase locked loop in detail, puts forward adaptive sampling scheme using single phase locked loop under variable frequency, increases accuracy of SVC sampling system. And tests response speed of phase locked loop via Real Time Digital Simulator for Power Systems (RTDS), through final verification in Fushun Lishizhai SVC Project, the design could meet system requirement for voltage phase accuracy.

Control divergence poses many problems in parallelizing loops. While predicated execution is commonly used to convert control dependence into data dependence, it often incurs high overhead because it allocates resources equally for both branches of a conditional statement regardless of their execution frequencies. For those loops with unbalanced conditionals, we propose a software transformation that divides a loop into two or three smaller loops so that the condition is evaluated only in the first loop, while the less frequent branch is executed in the second loop in a way that is much more efficient than in the original loop. To reduce the overhead of extra data transfer caused by the loop fission, we also present a hardware extension for a class of Coarse-Grained Reconfigurable Architectures (CGRAs). Our experiments using MiBench and computer vision benchmarks on a CGRA demonstrate that our techniques can improve the performance of loops over predicated execution by up to 65% (37.5%, on average), when the hardware extension is enabled. Without any hardware modification, our software-only version can improve performance by up to 64% (33%, on average), while simultaneously reducing the energy consumption of the entire CGRA including configuration and data memory by 22%, on average.

The mathematic model of third-order software phase locked loop formed by three-parameter loop filter is analyzed and designed. Then, in order to solve the problem of redundancy frequency analysis bandwidth when carrier tracking, a variable data ratio software phase locked loop is studied. Finally, the method is simulated and analyzed. The simulation results demonstrate that the software phase locked loop with variable data ratio can effectively reduce the operation capacity and improve the management efficiency of the software phase locked loop.

This paper proposes an efficient loop accelerator for a motion estimation specific instruction-set processor. ME algorithms in nature contain complex and multiple loop operations. To support efficient hardware (HW) loop operations, this paper introduces four loop instructions and their specific HW architecture. The simulation results show that the proposed loop accelerator can reduce about 29% average instruction cycles for ME early-termination schemes compared with typical implementation having a combination of compare and conditional jump instructions. The proposed loop accelerator of the motion estimation specific instruction-set processor can significantly reduce the number of program memory accesses and greatly save power consumption. Hence, it can be quite suitable for low power and flexible ME implementation.

Research on compiler techniques for thread-level loop speculation has so far remained on studying its performance limits: loop candidates that are worthy of parallelization are manually selected by the researchers or based on extensive profiling and preexecution. It is therefore difficult to include them in a production compiler for speculative multithreaded multicore processors. In a way, existing techniques are statically adaptive ("realized"; by the researchers for different inputs) yet dynamically greedy (since all iterations of all selected loop candidates are always parallelized at run time). This paper introduces a Statically GrEEdy and Dynamically Adaptive (SEED) approach for thread-level speculation on loops that is quite different from most other existing techniques. SEED relies on the compiler to select and optimize loop candidates greedily (possibly in an input-independent way) and provides a runtime scheduler to schedule loop iterations adaptively. To select loops for parallelization at runtime (subject to program inputs), loop iterations are prioritized in terms of their potential benefits rather than their degree of speculation as in many prior studies. In our current implementation, the benefits of speculative threads are estimated by a simple yet effective cost model. It comprises a mechanism for efficiently tracing the loop nesting structures of the program and a mechanism for predicting the outcome of speculative threads. We have evaluated SEED using a set of SPECint2000 and Olden benchmarks. Compared to existing techniques with a program's loop candidates being ideally selected a priori, SEED can achieve comparable or better performance while aututomating the entire loop candidate selection process.

SIMD (Single Instruction Multiple Data) extensions are acceleration components integrated in general processor, aiming at extracting instruction and data level parallelism of multimedia and scientific calculation programs. Currently, most of the automatic vectorization methods for SIMD architectures are based on innermost loops. Inner loop vectorization is the common approach for auto-vectorization. This method has been used for many years and its efficiency is widely accepted by people. In this paper, we put forward a better method than inner loop vectorization for some loop nests, which is outer loop vectorization. Outer loop vectorization method means vectorizing the outer loop directly. It can extract more data level parallelism and make the most use of the spatial locality to improve the program efficiency than the inner one which is more suitable for some loop nests. This paper presents the realization. In this paper, we first revisit the preliminary analysis of outer loop vectorization based on Open64 complier. And then, data type conversion and code generation is presented in detail. Finally, we propose two optimization methods, capable of boosting the performance of outer loop vectorization to achieve the acceleration of 20% on average, 50% at most.

Loops are challenging structures for program analysis, especially when loops contain multiple paths with complex interleaving executions among these paths. In this paper, we first propose a classification of multi-path loops to understand the complexity of the loop execution, which is based on the variable updates on the loop conditions and the execution order of the loop paths. Secondly, we propose a loop analysis framework, named Proteus, which takes a loop program and a set of variables of interest as inputs and summarizes path-sensitive loop effects on the variables. The key contribution is to use a path dependency automaton (PDA) to capture the execution dependency between the paths. A DFS-based algorithm is proposed to traverse the PDA to summarize the effect for all feasible executions in the loop. The experimental results show that Proteus is effective in three applications: Proteus can 1) compute a more precise bound than the existing loop bound analysis techniques; 2) significantly outperform state-of-the-art tools for loop verification; and 3) generate test cases for deep loops within one second, while KLEE and Pex either need much more time or fail.

Three-phase rectifier voltage often use software phase-locked loop, input voltage is appropriate. However, the software phase-locked loop had previously most locks can only perform accurate voltage in order that agreement cannot be done accurately lock in reverse order (lost key). To overcome this drawback in this article combines the principle of phase locked loop voltage argued upon, examined the nature of change of voltage vector angle reverse order, analyze the causes loss of lock reverse order part of a program to design self-adaptive phase locked loop can be done in the correct key sequence voltage and voltage upon reverse order. Also in this article also offer solutions using fractional integrated controller PIX to improve software self-adaptive phase locked loop instead of using the traditional PI controller as the software was designed before. Experimental results have demonstrated the method using fractional controllers to improve software PI phase locked loop three-phase self-adaptive software makes the phase locked loop to work more flexible, done properly locked voltage law in order upon agreement or otherwise. Carry extra one further step, analysis and experiments demonstrated using software adapts phase locked loop can make PWM (pulses width modulation) rectifiers work without influenced by the phase sequence of input voltage.

State-of-the-art compilers provide a large set of conservative optimizations that aim to improve the performance, most often omitting the energy consumption impact. Low Level Virtual Machine (LLVM) compiler infrastructure [1] has a dedicated set of optimizations for loops such as loop-invariant code motion, loop simply and many others. Each optimization is organized as a separate pass in LLVM [1] and a mix of object creational patterns is used to create the passes. This paper introduces a new loop optimization designed for LLVM [1], namely loop fusion. Loop fusion merges two successive loops by adding the content of the second loop into the first loop and deleting the second loop, when the following conditions are fulfilled: (1) the loops have to have the same number of iterations, (2) there should be no code between the two loops and (3) there should be no data dependencies between the two loops, that is the two loops should be independent (two loops are defined as dependent when the first loop needs to finish its processing, namely all its iterations, in order to start executing the second loop). The independence criterion is not equal to parallelism (e.g. two loops can be independent but it might not be possible to execute them in parallel). The fusion of two loops cuts in half the number of threads that would be otherwise required to execute them. By decreasing the number of threads, the parallelization overhead is reduced, thus the energy consumption is decreased. The impact of the loop fusion algorithm on both performance and energy consumption will be also discussed in this paper.

Loop optimizations span from vectorization, scalar promotion, loop invariant code motion, software pipelining to loop fusion, skewing, tiling and loop parallelization. These transformations are essential in the quest for automated high-performance code generation.Determining the validity of loop transformations at compile time requires analyzing all possible data dependences that may exist at run-time, i.e., all may-dependences. One fundamental issue faced by loop optimizers relates to the precision of alias and dependence information. Static alias and dependence analysis has been extensively studied, but many factors make the problem extremely tough.We provide theoretical and practical foundations to safely apply aggressive loop transformations on programs with polynomial data access relations. We do so by inverting how the may-dependence problem is attacked. Instead of providing alias information to the optimizer such that it can filter invalid transformations, we request that it performs a transformation that we believe will reduce the execution time and we generate a fast and precise test to validate, at run-time, if the optimization can be taken.

This paper proposes a method to implement the modified square loop digitally on the FPGA to solve the problem, that the divide circuit in the traditional square loop is difficult to achieve. The modified square loop has a similar structure to the traditional square loop. The method of modified square loop is to multiply quadrature output together to replace the divide circuit. In this paper, a specific method is given to digitize the square loop. The output carrier signal and the frequency difference will be analyzed in the condition of different initial frequency offset, parameters of the loop filter and input SNR.

This paper presents a loop-filter design method for third-order charge-pump phase-locked loops containing the loop delay. This method is derived from a z-domain phase-locked loop model. For a given loop bandwidth, we employ ripple swing control and adjust the filter pole to improve the spur performance. Another dynamic specification, the jitter peaking, is formulated as a H ∞ performance. The loop-filter design is transformed into an H ∞ optimization problem with the ripple swing constraint, which is solved using convex programming skills (linear matrix inequality, LMI). Compared to the conventional method, the method proposed in this study offers greater spur reduction without altering the loop bandwidth.

In order to improve anti-jamming performance of the sensor, fast lock digital PLL is proposed and the PLL is used in the sensor. Digital PLL with a simple structure, flexible control, high tracking accuracy, loop performance and easy integration of features; while PLL loop automatic variable in the model control technology to speed up the rate locked loop to reduce Phase jitter. In this paper, the arithmetic average and moving average value of the software filter scheme to solve the sensor can filter out high frequency interference filter design problems and improve robustness.

In contrast with the conventional split loop digital phase lock loop, a new loop is presented in this paper that differs from the earlier version principally by design aspects. It incorporates an additional phase modulation input along with its frequency modulation input in the digital controlled oscillator. It is capable of eliminating the deleterious effects of rounding and truncation error with faster signal accusation. Higher loop stability is also achievable using the new split loop digital phase lock loop. Furthermore, radio frequency filtering is done using an In phase and Quadrature phase (IQ) voltage controlled oscillator to avoid interaction between the loop filter and the radio frequency filter. Copyright © 2011 John Wiley & Sons, Ltd.

In this paper, we focused on the loop distribution system to solve the international issues of energy depletion and global warming. The conventional method of reconfiguration of distribution system was moving open points of switches from an actual switch position to another, while an appropriate switch must be opened to preserve the radial structure and this procedure is continued til there is no further loss reduction. However, the loop distribution system is the best optimization method to minimize loss than the other methods which is preserving radial structure. So we analyzed 3 types of loop distribution system upgraded from radial distribution system by changing normally open switch to normally closed switch. The simple 3 types of model system for simulation were composed, and each types of loop system were simulated in accordance with varying parameters. As a result of simulations, the loss reduction was different for each types of loop distribution system and each loop types have constraints for composing loop distribution system. The algorithms propose the method how to construct loop distribution system regarding constraints. Type I that needs least requirements get least loss reduction and Type III that needs most requirements get maximum loss reduction. On the other hand, Type I was most feasible distribution system to be realized.

Both reuse and concurrency are performance-critical for stream processors. When applying loop unrolling and software pipelining separately to stream-level loops, either reuse or concurrency or both may be inadequately exploited. In this paper, we optimize modulo scheduling to maximize stream reuse and improve concurrency for stream-level loops. The key insight is that an unrolled and software-pipelined stream-level loop could be described by a set of reuse equations. Guided by reuse equations, a reuse-aware modulo scheduling algorithm is developed to simultaneously optimize the two performance objectives, reuse, and concurrency, for a loop in a unified framework. Moreover, we describe a code generation algorithm to automatically produce the optimized loop from a given loop. The experimental results obtained on FT64 and by simulation demonstrate the effectiveness of the proposed approach.

This note proposes vibration-free motor control through modified LQG/LTR methodology. A conventional LQG/LTR method is a design tool in the frequency domain. However, unlike the conventional one, the proposed one is a time response based design method. This feature is firstly designed by parameterized settling time control gain through the target loop design procedure and the feature is secondly realized by loop transfer recovery. In order to show convergence to the target loop transfer functions, asymptotic behaviors of the open and the closed loop transfer functions are shown. At the conclusion, it is verified that the proposed method is robustly stable to parametric uncertainties through -plot.

In this paper, a technique that combines loop distribution with maximum direct loop fusion (LD_MDF) is proposed. The technique performs maximum loop distribution, followed by maximum direct loop fusion to optimize timing and code size simultaneously. The loop distribution theorems that state the conditions distributing any multi-level nested loop in the maximum way are proved. It is proved that the statements involved in the dependence cycle can be fully distributed if the summation of the edge weight of the dependence cycle satisfies a certain condition; otherwise, the statements should be put in the same loop after loop distribution. Based on the loop distribution theorems, algorithms are designed to conduct maximum loop distribution. The maximum direct loop fusion problem is mapped to the graph partitioning problem. A polynomial graph partitioning algorithm is developed to compute the fusion partitions. It is proved that the proposed maximum direct loop fusion algorithm produces the fewest number of resultant loop nests without violating dependence constraints. It is also shown that the resultant code size of the fused loops by the technique of loop distribution with maximum direct loop fusion is smaller than the code size of the original loops when the number of fused loops is less than the number of the original loops. The simulation results are presented to validate the proposed technique.

Double-delay tanlock loops with fractional and integer-order filters that are straightforward to implement are proposed. The amplitude, phase and frequency of the input signal are explicitly obtained with the aid of two delayed signals. Two types of loops are proposed: direct locking loop, where locking is achieved in a single sample but the loop does not have a filter, and an iterative locking loop, where locking is achieved using an integral iterative action. The iterative loop implements a filter, which governs the rate of locking and filters out unwanted noise. The iterative loop exhibits an attractive linear phase error detector with a period of 2π. Convergence and locking range analyses of first- and second-order loops are introduced. The loops with two time delays are not affected by the variation in signal power and have a wide locking range. The fractional-order dynamics of the digital loop filter increase the loop bandwidth which increases its bandwidth but makes it susceptible to noisy signals. A fifth-order loop filter can approximate an infinite dimensional fractional-order filter which can easily be implemented using existing fast DSP processors. The main points of this work are illustrated via numerical simulation.

The identification of closed loop systems has played an important role in the current context, since it reduces the operational costs of the identification process in the testing stage, reducing, for instance, off-spec production. However, in order to obtain the models, special care for treating the data is required. In this work, is presented a study on identification of linear models from closed loops operational data, based on the application of a virtual closed loop in the real loop. It consists of the virtual addition and removal of a controller to the analyzed loop, so as to filter the input of the system in a completely off-line procedure. This paper also propose modifications on this methodology resulting in an simplification of the virtual filter and in the ways to recover the open loop model.

In this article, we present a new technique for optimizing loops that contain kernels mapped on a reconfigurable fabric. We assume the Molen machine organization as our framework. We propose combining loop unrolling with loop shifting, which is used to relocate the function calls contained in the loop body such that in every iteration of the transformed loop, software functions (running on GPP) execute in parallel with multiple instances of the kernel (running on FPGA). The algorithm computes the optimal unroll factor and determines the most appropriate transformation (which can be the combination of unrolling plus shifting or either of the two). This method is based on profiling information about the kernel’s execution times on GPP and FPGA, memory transfers and area utilization. In the experimental part, we apply this method to several kernels from loop nests extracted from real-life applications (DCT and SAD from MPEG2 encoder, Quantizer from JPEG, and Sobel’s Convolution) and perform an analysis of the results, comparing them with the theoretical maximum speedup by Amdahl’s Law and showing when and how our transformations are beneficial.

Embedded systems have strict timing and code size requirements. Software pipelining is one of the most important optimization techniques to improve the execution time of loops by increasing the parallelism among successive loop iterations. However, there is no effective techniques exist for solving the software pipelining problem on nested loops. The existing software pipelining techniques for single loops can only explore the parallelism of the innermost loop, so the final timing performance is inferior. While multi-dimensional (MD) retiming can explore the outer loop parallelism, it introduces large overheads in loop index generation and code size due to loop transformation. In this paper, we show how the computation time and code size of a pipelined nested loop is affected by execution sequence and retiming, assuming there is no loop unfolding. We present the theory of Software PIpelining for NEsted loops (SPINE) to reveal the relationship among the computation time of an iteration, the execution sequence, and the software pipelining degree of a nested loop using retiming concepts. Two algorithms of Software PIpelining for NEsted loops (SPINE) are proposed based on the fundamental understanding of the properties of software pipelining for nested loops: the SPINE-FULL algorithm generates fully parallelized loops with the minimal overheads. The SPINE-ROW-WISE algorithm achieves the maximal parallelism in an iteration with a fixed row-wise execution sequence. Therefore, the overheads due to loop transformation are minimal. Our technique can be directly applied to imperfect nested loops. The experimental results show that the average improvement on the execution time of the pipelined loop generated by SPINE is 71.7% compared with that generated by the standard software pipelining technique. The average code size is reduced by 69.5% compared with that generated by the MD retiming technique.

Automated compiler analyses and transformation techniques aim at improving design productivity of the mapping process of applications expressed in high-level programming languages to FPGAs. These transformations allow a compiler tool to reduce the number of design cycles and eliminate tedious and error-prone low-level transformations required in this mapping process, while still leading to good designs. Scalar replacement, also known as register promotion, is a very important data-oriented transformation that leads to designs that reduce the number of external memory accesses, and thus reduce execution time, at the expense of storage resource's. In this article we present a combination of loop transformation techniques, namely loop unrolling, loop splitting, and loop interchange with scalar replacement to enable partial data reuse on computations expressed by tightly nested loops pervasive in image processing algorithms. We describe a performance modelling in the presence of partial data reuse. Our experi...

Register allocation is a much studied problem. A particularly important context for optimizing register allocation is within loops, since a significant fraction of the execution time of programs is often inside loop code. A variety of algorithms have been proposed in the past for register allocation, but the complexity of the problem has resulted in a decoupling of several important aspects, including loop unrolling, register promotion, and instruction reordering. In this paper, we develop an approach to register allocation and promotion in a unified optimization framework that simultaneously considers the impact of loop unrolling and instruction scheduling. This is done via a novel instruction tiling approach where instructions within a loop are represented along one dimension and innermost loop iterations along the other dimension. By exploiting the regularity along the loop dimension, and imposing essential dependence based constraints on intra-tile execution order, the problem of optimizing register pressure is cast in a constraint programming formalism. Experimental results are provided from thousands of innermost loops extracted from the SPEC benchmarks, demonstrating improvements over the current state-of-the-art.

Loop pipelining is widely adopted as a key optimization method in high-level synthesis (HLS). However, when complex memory dependencies appear in a loop, commercial HLS tools are still not able to maximize pipeline performance. In this paper, we leverage parametric polyhedral analysis to reason about memory dependence patterns that are uncertain (i.e., parameterised by an undetermined variable) and/or non-uniform (i.e., varying between loop iterations). We develop an automated source-to-source code transformation to split the loop into pieces, which are then synthesised by Vivado HLS as the hardware generation back-end. Our technique allows generated loops to run with a minimal interval, automatically inserting statically-determined parametric pipeline breaks at those iterations violating dependencies. Our experiments on seven representative benchmarks show that, compared to default loop pipelining, our parametric loop splitting improves pipeline performance by 4.3× in terms of clock cycles per iteration. The optimized pipelines consume 2.0× as many LUTs, 1.8× as many registers, and 1.1× as many DSP blocks. Hence the area-time product is improved by nearly a factor of 2.

The design method of the digital phase-locked loop is presented,according to the parameters of the center frequency, the loop filter bandwidth, etc. The modules,phase detector(PD), loop filter(LF), voltage controlled oscillator(VCO),have the similar behavior with that of the analog phase-locked loop(APLL) by using Laplace transform and bilinear transformation. For the case of lacking QuartusII license for numerical controlled oscillator(NCO) IP core, It can be replaced by the module designed by using triangle transform which is high-precision. Since enormous numbers of LEs in FPGA will be occupied by the multiplier of filters, the optimization algorithmis presented utilizingaddition operation and shifting operation rather than multiply operation, which reduces resources used on the system. The design result is simulated and realized on FPGA development board, which confirms that the design method is feasible. Introduction Phase-locked loop is widely used in the fields of electronics, communication, measurement and control, and automatic control. With the development of modern digital circuit technology, in the aspect of communication and control method of complex information processing can be implemented with the widely application of the microprocessor and VLSI. Phase-locked loop, as an important module in the communication fields, has the advantages of digital circuit in high reliability, low price, small volume and etc. Phase-locked loop is compatible with the digital circuit with better portability. Therefore, people pay more attention to the phase of the PLL, so that it is developed rapidly. With the development of digital devices, digital phase-locked loop is applied to signal processing, modulation and demodulation, weak signal detection, frequency synthesis and so on. Compared with the traditional analog phase-locked loop, the digital phase-locked loop does not have the case of temperature drift. The design circuit is simply, meanwhile, filter parameters and the numerical control oscillator source are controlled by the code. It is easy to build a variety of high order loop PLL. In this paper, according to the design example, design the parameters of the analog phase-locked loop. The digital processing of the analog parts is with the bilinear transformation. And use FPGA to simulate and implement it. Basic theory of phase-locked loop A typical phase-locked loop system is consist of three basic circuit components: Phase detector, loop filter and voltage controlled oscillator. As shown in Figure 1. Phase-detector detect phase deviation between input signal and feedback signal. Multiply the input signal with sinusoidal signal generated by a voltage controlled oscillator. Then the low pass filter is used to filter out the 4th National Conference on Electrical, Electronics and Computer Engineering (NCEECE 2015) © 2016. The authors Published by Atlantis Press 1471 radio-frequency component and get the phase difference between the input signal and the signal generated by the local oscillator. The phase difference is used as the control signal, controlling the voltage controlled oscillator by the correction network control network and using a negative feedback mechanism to reduce or eliminate the phase deviation of the input signal and the local oscillator signal. Fig 1.typical phase-locked loop The digital phase-locked loop samples the analog input signal by the A/D into the FPGA. In FPGA, a phase detector, loop filter, and a numerical control oscillator module are built, making it to meet the same or similar operating performance of the analog filter. Requirements of design examples Designing an ideal two order loop digital phase-locked loop, carrier-frequency is 10 , maximum modulating angular frequency is 103π rad/s, 400 2π rad/s, 0.707。 According to the design requirements, the natural resonance frequency is: . 50π rad/s (1) Tap parameters of loop filter: 0.10053 (2)

Loop parallelization and loop vectorization of array-intensive programs are two common transformations applied by parallelizing compilers to convert a sequential program into a parallel program. Validation of such transformations carried out by untrusted compilers are extremely useful. This paper proposes a novel algorithm for construction of the dependence graph of the generated parallel programs. The transformations are then validated by checking equivalence of the dependence graphs of the original sequential program and the parallel program using a standard and fairly general algorithm reported elsewhere in the literature. The above equivalence checker still works even when the above parallelizing transformations are preceded by various enabling transformations except for loop collapsing which changes the dimensions of the arrays. To address the issue, the present work expands the scope of the checker to handle this special case by informing it of the correspondence between the index spaces of the corresponding arrays in the sequential and the parallel programs. The augmented algorithm is able to validate a large class of static affine programs. The proposed methods are implemented and tested against a set of available benchmark programs which are parallelized by the polyhedral auto-parallelizer LooPo and the auto-vectorizer Scout. During experiments, a bug of the compiler LooPo on loop parallelization has been detected.

Software pipelining is an efficient method of loop optimization that allows for parallelism of operations related to different loop iterations. Currently, most commercial compilers use loop pipelining methods based on modulo scheduling algorithms. This paper reviews these algorithms and considers algorithmic solutions designed for overcoming the negative effects of software pipelining of loops (a significant growth in code size and increase in the register pressure) as well as methods making it possible to use some hardware features of a target architecture. The paper considers global-scheduling mechanisms allowing one to pipeline loops containing a few basic blocks and loops in which the number of iterations is not known before the execution.

Traditionally, loop nests are fused only when the data dependences in the loop nests are not violated. This paper presents a new loop fusion algorithm that is capable of fusing loop nests in the presence of fusion-preventing anti-dependences. All the violated anti-dependences are removed by automatic array copying. As a case study, this aggressive loop fusion strategy is applied to a Jacobi solver. The performance of iterative methods is typically limited by the speed of the memory system. Fusing the two loop nests in the Jacobi solver into one reduces data cache misses, and consequently, improves the performance results of both sequential and parallel versions of the Jacobi program, as validated by our experimental results on an HP AlphaServer SC45 supercomputer.