In this paper, we present a first solution to the unsolved problem of joint tiling and scheduling a given loop nest with uniform data dependencies symbolically. This problem arises for loop programs for which the iter...
详细信息
ISBN:
(纸本)9781479904945;9781479904938
In this paper, we present a first solution to the unsolved problem of joint tiling and scheduling a given loop nest with uniform data dependencies symbolically. This problem arises for loop programs for which the iterations shall be optimally scheduled on a processor array of unknown size at compile-time. Still, we show that it is possible to derive parameterized latency-optimal schedules statically by proposing two new program transformations: In the first step, the iteration space is tiled symbolically into orthotopes of parametrized extensions. The resulting tiled program is subsequently scheduled symbolically. Here, we show that the maximal number of potential optimal schedules is upper bounded by 2(n)n! where n is the dimension of the loop nest. However, the real number of optimal schedule candidates being much less than this. 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 activated and the corresponding program configuration executed on the resulting processor array so to avoid any further run-time optimization or expensive re-compilations.
form only given. Hybrid systems are composed by continuous physical component and discrete control component where the system state evolves over time according to interacting law of discrete and continuous dynamics. C...
详细信息
ISBN:
(纸本)9780769550077
form only given. Hybrid systems are composed by continuous physical component and discrete control component where the system state evolves over time according to interacting law of discrete and continuous dynamics. Combinations of computation and control
The incorporation of error detection and recovery mechanisms becomes mandatory as the probability of the occurrence of transient faults increases. The detection of control flow errors has been extensively investigated...
详细信息
ISBN:
(纸本)9781479915859;9781479915835
The incorporation of error detection and recovery mechanisms becomes mandatory as the probability of the occurrence of transient faults increases. The detection of control flow errors has been extensively investigated in literature. However, only few works have been conducted towards recovery from control-flow errors. Generally, a program is re-executed after error detection. Although re-execution prevents faults from corrupting data, it does not allow the application to run to completion correctly in the presence of an error. Moreover, the overhead of re-execution increases prominently. The current study presents a pure-software method based on encoded signatures to recover from control-flow errors. Unlike general signature monitoring techniques, the proposed method targets not only interblock transitions, but also intrablock and inter-function transitions. After detecting the illegal transition, the program flow transfers back to the block where the error occurred, and the data errors caused by the error propagation are recovered. Fault injection and performance overhead experiments are performed to evaluate the proposed method. The experimental results show that most control flow errors can be recovered with relatively low performance overhead.
This paper evaluates the impact on reliability in the control-flow of programs that compiler optimizations incur in terms of fault coverage for the Automatic Correction of control-flow Errors technique. This technique...
详细信息
ISBN:
(纸本)9781467357470;9780769549293
This paper evaluates the impact on reliability in the control-flow of programs that compiler optimizations incur in terms of fault coverage for the Automatic Correction of control-flow Errors technique. This technique was implemented in the LLVM framework, enabling the automated analysis of programs. In order to evaluate the efficiency of the technique of fault tolerance we performed a series of fault injection experiments using the MiBench benchmark suite as case study, measuring how individual and combined optimizations impact reliability.
In this paper, we analyze termination of multipath linear loop programs by combining the trial difference method and calculation of loop complexity upper bound. Though this method is not complete, it is useful to veri...
详细信息
In the process of program reverse analyzing, anti-track instruction and indirect jump instruction is common to see and difficult to be automatic disassembly analyzed. This article gives a kind of algorithm to adjust p...
详细信息
This paper deals with the estimation of a gramian-based interaction measure from logged process data, and thereby removing the need of creating parametric models prior to the selection of the significant input-output ...
详细信息
ISBN:
(纸本)9781612848006
This paper deals with the estimation of a gramian-based interaction measure from logged process data, and thereby removing the need of creating parametric models prior to the selection of the significant input-output interconnections. Moreover, the resulting confidence regions of the estimates can be used to perform a robust control structure selection. The considered interaction measure is the Participation Matrix. Based on previous results, a new unbiased statistic is proposed, and confidence bounds for the estimate are derived. Examples and a case study are used to illustrate how the method can be applied.
This paper deals with the binary analysis of executable programs, with the goal of understanding how they access memory. It explains how to statically build a formal model of all memory accesses. Starting with a contr...
详细信息
ISBN:
(纸本)9780769541785
This paper deals with the binary analysis of executable programs, with the goal of understanding how they access memory. It explains how to statically build a formal model of all memory accesses. Starting with a control-flow graph of each procedure, well-known techniques are used to structure this graph into a hierarchy of loops in all cases. The paper shows that much more information can be extracted by performing a complete data-flow analysis over machine registers after the program has been put in static single assignment (SSA) form. By using the SSA form, registers used in addressing memory can be symbolically expressed in terms of other, previously set registers. By including the loop structures in the analysis, loop indices and trip counts can also often be expressed symbolically. The whole process produces a formal model made of loops where memory accesses are linear expressions of loop counters and registers. The paper provides a quantitative evaluation of the results when applied to several dozens of SPEC benchmark programs. Because static analysis is often incomplete, the paper ends by describing a lightweight instrumentation strategy that collects at run time enough information to complete the program's symbolic description.
Loop invariants play a major role in program verification. Though various techniques have been applied to automatic loop invariants generation, most interesting ones often generate only candidate invariants. Thus, a k...
详细信息
ISBN:
(纸本)9781424486298
Loop invariants play a major role in program verification. Though various techniques have been applied to automatic loop invariants generation, most interesting ones often generate only candidate invariants. Thus, a key issue to take advantage of these invariants in a verification process is to check that these candidate loop invariants are actual invariants. This paper introduces a new technique based on constraint programming for automatic verification of inductive loop invariants. This approach is efficient to detect spurious invariants and is also able to verify valid invariants under boundedness restrictions. First experiments on classical benchmarks are very promising.
This paper presents the use of LALP to implement typical industrial application kernels, ADPCM Encoder and Decoder, in FPGAs. LALP is a domain specific language and its compilation framework aims to the direct mapping...
详细信息
ISBN:
(纸本)9781424463916
This paper presents the use of LALP to implement typical industrial application kernels, ADPCM Encoder and Decoder, in FPGAs. LALP is a domain specific language and its compilation framework aims to the direct mapping of algorithms originally described in a high-level language onto FPGAs. In particular, LALP focuses on loop pipelining, a key technique for the design of hardware accelerators. While the language syntax resembles C, it contains certain constructs that allow programmer interventions to enforce or relax data dependences as needed, and so optimize the performance of the generated hardware. We present experimental results showing significant performance gains using this approach, while still keeping the language syntax and semantics close to popular high level software languages, a desirable feature when considering time to market constraints. We believe the performance gains observed for the ADPCM implementation can be extended to other industrial applications relying on algorithms spending most of their execution time on loop structures, such signal and image processing.
暂无评论