The paper presents the ongoing work of studying FMEA method for embedded safely critical software via formal analysis of various dependence relations among software elements, which can fairly improve the automation an...
详细信息
The paper presents the ongoing work of studying FMEA method for embedded safely critical software via formal analysis of various dependence relations among software elements, which can fairly improve the automation and precision of both system level and detailed level FMEA. These dependence relations are depicted by the formal models abstracted from software design and implementation, and the FMEA processes for both structural and object-oriented software are proposed respectively. The initial result of case study shows the effectiveness of the approach.
The goal of the least areas path problem (LAPP) is to find a path traversing through a given region covered by a set of areas with any arbitrary shape, between a given pair of points and with the property that each po...
详细信息
The goal of the least areas path problem (LAPP) is to find a path traversing through a given region covered by a set of areas with any arbitrary shape, between a given pair of points and with the property that each point on the path is covered by the least areas. Different the weighted region optimal path problem, the LAPP asks for the cost of each step in path is as low as possible. Based on the relationship between boundaries of sub-regions and the least areas path, we can transform this continuous-domain problem to a discrete one by calculating the coverage of curves of sub-regionspsila boundaries. Depending on binary-search and breadth-first-search, an efficient and fast algorithm was devised for solving the LAPP.
Application-level checkpointing can decrease the overhead of fault tolerance by minimizing the amount of checkpoint data. However this technique requires the programmer to manually choose the critical data that should...
详细信息
ISBN:
(纸本)9781424431748
Application-level checkpointing can decrease the overhead of fault tolerance by minimizing the amount of checkpoint data. However this technique requires the programmer to manually choose the critical data that should be saved. In this paper, we firstly propose a live-variable analysis method for MPI programs. Then, we provide an optimization method of data saving for application-level check-pointing based on the analysis method. Based on the theoretical foundation, we implement a source-to-source pre-compiler (ALEC) to automate application-level checkpointing. Finally, we evaluate the performance of five FOR-TRAN/MPI programs which are transformed and integrated checkpointing features by ALEC on a 512-CPU cluster system. The experimental results show that i)the application-level checkpointing based on live-variable analysis for MPI programs can efficiently reduce the amount of checkpoint data, thereby decrease the overhead of checkpoint and restart;ii)ALEC is capable of automating application-level checkpointing correctly and effectively.
One of the basic problems related to the efficient application-level checkpointing is the placement of checkpoints in the source codes. In this paper we discuss two common questions with a source-to-source precompiler...
详细信息
One of the basic problems related to the efficient application-level checkpointing is the placement of checkpoints in the source codes. In this paper we discuss two common questions with a source-to-source precompiler ALEC: 1) if there are N checkpoints in the application's source code, how to pick M checkpoints out of them minimizing the total amount of checkpoint data? 2) if there are no checkpoint in the application's source code, how to insert a set of checkpoints minimizing the amount of checkpoint data? We reveal that these two questions can both be abstracted as a mathematic model which is similar to the 0-1 integer programming model, and the model can be solved using implicit enumeration method. The solving methods proposed in the paper have been implemented and integrated into ALEC. Experimental results show that the method is efficient.
Application-level checkpointing is a promising technology in the domain of large-scale scientific computing. The consistency of global checkpoint must be carefully guaranteed in order to correctly restore the computat...
详细信息
Application-level checkpointing is a promising technology in the domain of large-scale scientific computing. The consistency of global checkpoint must be carefully guaranteed in order to correctly restore the computation. Usually, some complex coordinated protocols are employed to ensure the consistency of global checkpoint, which require logging orphan or in-transit messages during checkpointing. These protocols complicate the recovery of the computation and increase the checkpoint overhead due to logging message. In this paper, a new method which ensures the consistency of global checkpoint by static analysis is proposed. The method identifies the safe checkpointing regions in MPI programs, where the global checkpoint is always strongly consistent. All checkpoints are located in those safe checkpoint regions. During checkpointing, the method will not log any messages and introduce no extra overhead. The method was implemented and integrated into ALEC, which is a source-to-source precompiler for automating application-level checkpointing. The experimental results show that our method is effective.
In this paper we describe load scheduling, a novel method that balances load among register files by residual resources. Load scheduling can reduce register pressure for clustered VLIW processors with distributed regi...
ISBN:
(纸本)9781424419227
In this paper we describe load scheduling, a novel method that balances load among register files by residual resources. Load scheduling can reduce register pressure for clustered VLIW processors with distributed register files while not increasing VLIW scheduling length. We have implemented load scheduling in compiler for Imagine and FT64 stream processors. The result shows that the proposed technique effectively reduces the number of variables spilled to memory, and can even eliminate it. The algorithm presented in this paper is extremely efficient in embedded processor with limited register resource because it can improve registers utilization instead of increasing the requirement for the number of registers.
This chapter presents a formalization of functional and behavioural requirements, and a refinement of requirements to a design for CoCoME using the Relational Calculus of Object and Component Systems (rCOS). We give a...
详细信息
The weapon-target assignment (WTA) problem is a fundamental problem arising in defense-related applications of operations research. The WTA problem can be formulated as a nonlinear integer programming problem and is k...
详细信息
The weapon-target assignment (WTA) problem is a fundamental problem arising in defense-related applications of operations research. The WTA problem can be formulated as a nonlinear integer programming problem and is known to be NP-complete. We present firstly a technique founded on the use weapon cell, which enables one-to-many mapping about weapon-target to become one-to-one mapping. Next, we introduce a framework of solving the WTA problem. Based on this framework, an approximation algorithm that is grounded on the rules about weapon cells and targets is proposed. Finally, the simulative results show that the proposed algorithm indeed is very efficient.
Most proposed DHTs have their unique maintenance mechanisms specific to the static graphs on which they are based. In this paper we propose distributed line graphs (DLG), a universal framework for building DHTs based ...
详细信息
ISBN:
(纸本)9781424431748
Most proposed DHTs have their unique maintenance mechanisms specific to the static graphs on which they are based. In this paper we propose distributed line graphs (DLG), a universal framework for building DHTs based on arbitrary constant-degree graphs. We prove that in a DLG-enabled, N-node DHT, the out-degree is d, the in-degree is between 1 and 2d, and the diameter is less than 2(log d N-log d N 0 +D 0 +1), where d, D 0 and N 0 represent the degree, diameter and number of nodes of the initial graph, respectively. The maintenance cost of DLG-enabled DHTs is O(log d N). We show the power of DLG technique by applying it to Kautz graphs to propose a new DHT scheme.
In most DHTs proposed so far, all nodes are assumed to be homogeneous, and all messages are routed using a common algorithm. In practice, however, nodes in large-scale systems might be heterogeneous with respect to th...
详细信息
In most DHTs proposed so far, all nodes are assumed to be homogeneous, and all messages are routed using a common algorithm. In practice, however, nodes in large-scale systems might be heterogeneous with respect to their capabilities, reputations, affiliations of administrative domains, and so on, which consequently makes it preferable to distinguish the heterogeneity of participant nodes. To achieve this, in this paper we present grouped tapestry (GTap), a novel tapestry-based DHT that supports organizing nodes into groups and allows flexible DHT routing. The effectiveness of our proposals is demonstrated through theoretical analysis and extensive simulations.
暂无评论