A framework for data-flow distributed processing

A framework for data-flow distributed processing is established through the definition of a data-flow model and a set of language constructs for concurrent programming. The proposed approach is based on the following characteristics: i) the exploitation of parallelism at the operation level leads to the efficient and natural exploitation of parallelism at the program level, and ii) parallelism, communication, nondeterminism and history sensitivity are primitive concepts. The aim of the defined data-flow constructs is to enhance modularity and parallelism of programs. Two structuring levels are introduced, called «modules» and «frames», to permit both symmetric and asymmetric communication. Single assignment and guarded commands are employed inside modules. Examples of tipical programming problems, including shared resources management, are given together with a short account of a distributed data-flow architecture able to support data-flow distributed processing efficiently.     

Optimization of very high level languages—I: Value transmission and its corollaries

SETL is a set-theoretically oriented language of very high level whose repertoire of semantic objects includes finite sets, ordered n-tuples, and sets of ordered n-tuples useable as mappings. This two-part paper studies the optimization problems associated with such a language. The first issue studied is that of copy optimization, i.e. the discovery of cases in which changes to a compound data object can be made ‘differentially’ without recopying the whole of the object. The second part of the paper sets forth techniques for the automatic discovery of relationships of inclusion and membership on which automatic data-structure choice may be based. The methods used extend known techniques of data-flow analysis and of logical program analysis.     

Structural analysis: A new approach to flow analysis in optimizing compilers

In this paper we present a new technique for analyzing the control flow of a computer program. This technique, called structural analysis, extends new interval analysis techniques and produces a program representation in which structured control-flow patterns are detected and recorded. This representation supports data-flow analysis elimination techniques similar to Rosen's high-level data-flow analysis technique, which are faster than interval-based methods. Morever, these results indicate that flow-graph based program analysis and direct analysis of the program's parse-tree can be performed by essentially the same methods, making uniform data-flow analysis procedure for optimizing compilers possible.     

Optimization of very high level languages—II. Deducing relationships of inclusion and membership

SETL is a set-theoretically oriented language of very high level whose reportoire of semantic objects includes finite sets, ordered n-tuples, and sets of ordered n-tuples useable as mappings. This two-part paper studies the optimization problems associated with such a language. The first issue studied is that of copy optimization, i.e. the discovery of cases in which changes to a compound data object can be made “differentially” without recopying the whole of the object. The second part of the paper sets forth techniques for the automatic discovery of relationships of inclusion and membership on which automatic data-structure choice may be based. The methods used extend known techniques of data-flow analysis and of logical program analysis.     

在线挖掘数据流闭合频繁项集CMNL-SW算法

提出了一种新的CMNL-SW(Closed map and num list-sliding window)挖掘算法。具体使用数据结构Closedmap存储挖掘到的闭合项集和Num list存储所有不同项的序号,通过对添加新事务和删除旧事务包含的项序号进行简单的并集和该事务与之相关已经挖掘到的闭合项集进行交集运算来更新当前滑动窗口,使之能够根据用户任意指定的支持度阈值在线输出数据流上闭合频繁项集信息。通过理论分析和对真实数据集Mushroom,Retail-chain和人工合成数据集T40I10D100K的挖掘结果表明,提出的算法在时空效率上明显优于同类经典算法Moment和CFI-Stream,并且随着数据流上处理事务数的递增和快速改变表现出良好的稳定性。     

Automated software test data generation

An alternative approach to test-data generation based on actual execution of the program under test, function-minimization methods and dynamic data-flow analysis is presented. Test data are developed for the program using actual values of input variables. When the program is executed, the program execution flow is monitored. If during program execution an undesirable execution flow is observed then function-minimization search algorithms are used to automatically locate the values of input variables for which the selected path is traversed. In addition, dynamic data-flow analysis is used to determine those input variables responsible for the undesirable program behavior, significantly increasing the speed of the search process. The approach to generating test data is then extended to programs with dynamic data structures and a search method based on dynamic data-flow analysis and backtracking is presented. In the approach described, values of array indexes and pointers are known at each step of program execution; this information is used to overcome difficulties of array and pointer handling     

Using Verified Data-Flow Analysis-based Optimizations in Attribute Grammars

Building verified compilers is difficult, especially when complex analyses such as type checking or data-flow analysis must be performed. Both the type checking and program optimization communities have developed methods for proving the correctness of these processes and developed tools for using, respectively, verified type systems and verified optimizations. However, it is difficult to use both of these analyses in a single declarative framework since these processes work on different program representations: type checking on abstract syntax trees and data-flow analysis-based optimization on control flow or program dependency graphs.We present an attribute grammar specification language that has been extended with constructs for specifying attribute-labelled control flow graphs and both CTL and LTL-FV formulas that specify data-flow analyses. These formulas are model-checked on these graphs to perform the specified analyses. Thus, verified type rules and verified data-flow analyses (verified either by hand or with automated proof tools) can both be transcribed into a single declarative framework based on attribute grammars to build a high-confidence language implementations. Also, the attribute grammar specification language is extensible so that it is relatively straight-forward to add new constructs for different temporal logics so that alternative logics and model checkers can be used to specify data-flow analyses in this framework.     

含指针程序的单子切片方法

传统的含指针程序切片方法将指向分析与切片计算分开,增加了一定系统开销,为此文中提出一种可同时进行切片计算和指向分析的单子切片算法.该算法将程序正向切片思想与数据流迭代分析相结合,它是流敏感的,具有一定的精度,而且因指向分析和切片计算同时进行,故不需要像一般的流敏感分析方法那样记录每一个程序点的指向信息,而只需记录当前所分析的程序点处指向信息,从而节省了存储空间.此外,它还继承了原有单子切片方法所具有的强语言适应性和组合性.     

Operations on fuzzy sets—an axiomatic approach

We introduce intersection and union of fuzzy sets, constructed by means of operations on the unit interval which may depend on the considered element of the universe of discourse. A similar approach for complementation was given by Lowen [7]. The main result is that element-dependent operations are not compatible with the preservation of the intersection and union under the inverse image of a function. Finally we consider fuzzy σ-algebras built with these set-theoretic operations.     

Strategy for data-flow synchronizations in stencil parallel computations on multi-/manycore systems

In this paper, an innovative strategy for the data-flow synchronization in shared-memory systems is proposed. This strategy assumes to synchronize only interdependent threads instead of using the barrier approach that—in contrast to our approach—synchronize all threads. We demonstrate the adaptation of the data-flow synchronization strategy to two complex scientific applications based on stencil codes. An algorithm for the data-flow synchronization is developed and successfully used for both applications. The proposed approach is evaluated for various Intel microarchitectures released in the last 5 years, including the newest processors: Skylake and Knights Landing. The important part of this assessment is the performance comparison of the proposed data-flow synchronization with the OpenMP barrier. The experimental results show that the performance of the studied applications can be accelerated up to 1.3 times using the proposed data-flow synchronizations strategy.     

基于SMT的区域控制器同步反应式模型的形式化验证

在安全关键系统的软件开发过程中,形式化验证是一种经检验的提高软件质量的技术.然而,无论从理论上还是从应用角度来看,软件的验证都必须是完整的,数据流验证应该是对实现层软件模型进行验证的必要体现.因此,环境输入、泛型函数、高阶迭代运算和中间变量对于分析形式化验证的可用性至关重要.为了验证同步反应式模型,工程师很容易验证控制流模型(即安全状态机).现有工作表明,这类工作无法全面地验证安全关键系统的同步反应式模型,尤其是数据流模型,导致这些方法没有达到工业应用的要求,这成为对工业安全软件进行形式化验证的一个挑战.提出了一种自动化验证方法.该方法可以实现对安全状态机和数据流模型的集成进行验证.采用了一种基于程序综合的方法,其中,SCADE模型描述了功能需求、安全性质和环境输入,可以通过对Lustre模型的程序综合,采用基于SMT的模型检查器进行验证.该技术将程序合成作为一种通用原理来提高形式化验证的完整性.在轨道交通的工业级应用(近200万行Lustre代码)上评估了该方法.实验结果表明,该方法在大规模同步反应式模型长期存在的复杂验证问题上是有效的.     

基于二进制的集合运算研究

通过比较二进制与集合之间的内在联系,提出了基于二进制的集合运算思想,给出了基于二进制的各种集合运算算法,该算法有效解决了传统集合操作算法中运算速度慢,效率低的不足,并提供了求幂集,交集,并集等集合运算算法的c语言源程序。     

一个基于Vague集相似度量的近似推理方法

对文献[1]中提出的一种基于Vague集之间相似程度的度量方法进行了分析，指出了这种相似度量方法存在的缺陷。在此基础上，给出了一种改进的相似度量方法。同时，我们还给出了一种新的Vague集的交并运算规则，并在新的交并运算基础上，提出了一种基于Vague集相似度量的近似推理方法。最后，用实例说明了这种近似推理的推理过程。     

新型软亚BCI-代数的进一步研究

提出了两个亚BCI-代数的并代数、两个软集在并代数上的扩展交、软集的软平移以及两个软集的合成运算等新概念。举例说明了并代数以及在并代数上扩展交的存在性。证明了两个新型软亚BCI-代数在一定的条件下在并代数上的扩展交仍然是新型软亚BCI-代数。研究了新型软亚BCI-代数的软平移及投影等的相关性质。另外,利用两个软集的合成运算、软集的水平集以及广义特征函数分别给出了新型软亚BCI-代数的等价刻画。     

May/must analysis and the DFAGen data-flow analysis generator

Data-flow analysis is a common technique for gathering program information for use in program transformations such as register allocation, dead-code elimination, common subexpression elimination, and scheduling. Current tools for generating data-flow analysis implementations enable analysis details to be specified orthogonally to the iterative analysis algorithm but still require implementation details regarding the may and must use and definition sets that occur due to the effects of pointers, side effects, arrays, and user-defined structures. This paper presents the Data-Flow Analysis Generator tool (DFAGen), which enables analysis writers to generate analyses for separable and nonseparable data-flow analyses that are pointer, aggregate, and side-effect cognizant from a specification that assumes only scalars. By hiding the compiler-specific details behind predefined set definitions, the analysis specifications for the DFAGen tool are typically less than ten lines long and similar to those in standard compiler textbooks. The main contribution of this work is the automatic determination of when to use the may or must variant of a predefined set usage in the analysis specification.     

基于t-模的区间值模糊的截集性质研究

区间值模糊集的隶属度使其拥有更多的自由度。从而在处理信息不确定性和模糊性时比经典模糊集更有优势。为了更好地利用区间模糊集,研究其截集及性质具有重要的意义。本文首先定义了一种基于t-模的区间值模糊集的截集,进一步讨论了基于t-模的区间值模糊集的广义交、并、补的截集的相关性质。特别地,若T(S)为∧(∨)-可表示的,则区间模糊集的交、并、补运算与截集运算可交换。     

结合扩展规则重构的#SAT问题增量求解方法

#SAT问题是人工智能中的重要问题,在人工智能领域被广泛应用.在对基于扩展规则的模型计数求解方法CER深入研究的基础上,重构CER中使用的计算公式,并对其正确性进行了证明;提出极大项相交集和扩展极大项相交集的概念,并给出根据两者关系重用极大项相交集计算结果的增量求解方法,且对广义互补子句集对应的所有扩展极大项相交集进行剪枝,有效避免了计算所有极大项相交集对应极大项个数时的冗余求解;提出构建记录子句间互补关系的互补表方法,给出重用极大项相交集基础子句集互补结果的增量互补判定方法,较好地避免了判断子句间和各极大项相交集的基础子句集互补关系时的重复计算.实验结果表明:RCER方法易于实现,扩展性强,比CER方法效率更高,尤其是在互补因子较低时,效率提升更为显著.     

双布鲁姆过滤器法查询集合成员

探讨双布鲁姆过滤器查询法查询集合并集、交集、补集、差集或对称差成员的性能问题。理论分析和实验结果表明,双布鲁姆过滤器查询法能够较好地支持集合并集、交集、补集、差集及对称差的成员查询问题,其中双布鲁姆过滤器并集及交集查询不会产生假阴性,仅有少量假阳性的存在,而双布鲁姆过滤器补集、差集及对称差查询则除存在少量假阳性外,还存在少量假阴性。     

Keeping calm in the face of change

Functional Reactive Programming (FRP) is an approach to reactive programming where systems are structured as networks of functions operating on signals (time-varying values). FRP is based on the synchronous data-flow paradigm and supports both (an approximation to) continuous-time and discrete-time signals (hybrid systems). What sets FRP apart from most other languages for similar applications is its support for systems with dynamic structure and for higher-order reactive constructs.     

The relationship among soft sets,soft rough sets and topologies

Molodtsov’s soft set theory is a newly emerging tool to deal with uncertain problems. Based on the novel granulation structures called soft approximation spaces, Feng et al. initiated soft rough approximations and soft rough sets. Feng’s soft rough sets can be seen as a generalized rough set model based on soft sets, which could provide better approximations than Pawlak’s rough sets in some cases. This paper is devoted to establishing the relationship among soft sets, soft rough sets and topologies. We introduce the concept of topological soft sets by combining soft sets with topologies and give their properties. New types of soft sets such as keeping intersection soft sets and keeping union soft sets are defined and supported by some illustrative examples. We describe the relationship between rough sets and soft rough sets. We obtain the structure of soft rough sets and the topological structure of soft sets, and reveal that every topological space on the initial universe is a soft approximating space.