A new approach to pointer analysis for assignments

Pointer analysis is a technique to identify at copile-time the potential values of the pointer expressions in a program,which promises significant benefits for optimzing and parallelizing complilers.In this paper,a new approach to pointer analysis for assignments is presented.In this approach,assignments are classified into three categories:pointer assignments,structure(union)assignents and normal assignments which don‘t affect the point-to information.Pointer analyses for these three kinds of assignments respectively make up the integrated algorithm.When analyzing a pointer assigemtn.a new method called expression expansion is used to calculate both the left targets and the right targets.The integration of recursive data structure analysis into pointer analysis is a significant originality of this paper,which uniforms the pointer analysis for heap variables and the pointer analysis for stack variables.This algorithm is implemented in Agassiz,an analyzing tool for C programs developed by Institute of Parallel Processing,Fudan University,Its accuracy and effectiveness are illustrated by experimental data.     

An optimal adaptive routing algorithm

An adaptive routing algorithm for packet-switched networks is proposed. This algorithm updates both the estimate of external traffic input and the routing assignments at each iteration. The routing assignments determine the proportions of the traffic destined for nodejto be sent from nodeithrough the outgoing links ofi. The algorithm maintains the loop freedom of the routing assignment at each iteration. It also achieves the minimum delay of the network as the limit of its successive updating procedure. The additional features of the algorithm are that it allows at any iteration some routing assignments which theoretically induce infinite delay and that it may utilize variable scaling factors to speed up the convergence.     

Winnowing算法和动态规划算法在作业剽窃检测中的应用和比较

信息数字化后使抄袭、剽窃变得更加容易了,为了杜绝学生作业中出现的抄袭现象,急需高效的剽窃检测技术,帮助教师对学生作业的抄袭情况实施监督检测。本文分别用具有除噪和过滤功能的Winnowing算法和动态规划算法对学生作业进行剽窃检测。通过对文档间相似度的对比,实现了对作业剽窃程度的检测。实验结果表明,Winnowing算法更加有效、更加可靠。     

Optimizing vote and quorum assignments for reading and writingreplicated data

In the weighted voting protocol which is used to maintain the consistency of replicated data, the availability of the data to ready and write operations not only depends on the availability of the nodes storing the data but also on the vote and quorum assignments used. The authors consider the problem of determining the vote and quorum assignments that yield the best performance in a distributed system where node availabilities can be different and the mix of the read and write operations is arbitrary. The optimal vote and quorum assignments depend not only on the system parameters, such as node availability and operation mix, but also on the performance measure. The authors present an enumeration algorithm that can be used to find the vote and quorum assignments that need to be considered for achieving optimal performance. When the performance measure is data availability, an analytical method is derived to evaluate it for any vote and quorum assignment. This method and the enumeration algorithm are used to find the optimal vote and quorum assignment for several systems. The enumeration algorithm can also be used to obtain the optimal performance when other measures are considered     

A fast parallel algorithm for routing unicast assignments in Benesnetworks

This paper presents a new parallel algorithm for routing unicast (one-to-one) assignments in Benes networks. Parallel routing algorithms for such networks were reported earlier, but these algorithms were designed primarily to route permutation assignments. The routing algorithm presented in this paper removes this restriction without an increase in the order of routing cost or routing time. We realize this new routing algorithm on two different topologies. The algorithm routes a unicast assignment involving O(k) pairs of inputs and outputs in O(lg ² k+lg n) time on a completely connected network of n processors and in O(lg⁴ k+lg² k lg n) time on an extended shuffle-exchange network of n processors. Using O(n lg n) professors, the same algorithm can be pipelined to route α unicast assignments each involving O(k) pairs of inputs and outputs, in O(lg² k+lg n+(α-1) lg k) time on a completely connected network and in O(lg⁴ k+lg² k lg n+(α-1)(lg ³ k+lg k lg n)) time on the extended shuffle-exchange network. These yield an average routing time of O(lg k) in the first case, and O(lg³ k+1g k lg n) in the second case, for all α⩾lg n. These complexities indicate that the algorithm given in this paper is as fast as Nassimi and Sahni's algorithm for unicast assignments, and with pipelining, it is faster than the same algorithm at least by a factor of O(lg n) on both topologies. Furthermore, for sparse assignments, i.e., when k=O(1), it is the first algorithm which has an average routing time of O(1g n) on a topology with O(n) links     

网上任务分派问题数学实验的可视化设计

研究了各种任务分派问题算法,对一般任务分派和有约束任务分配的求解方法进行算法设计,以Microsoft Visual J++6.0作为实验开发平台,采用Java语言及Applet嵌入网页技术,实现了网上任务分派问题数学实验的可视化。用户可由可视化界面,输入任意任务分配问题,得到最佳的分配结果及满意率。为学生学习掌握相关知识,提供了具有可视化和交互性功能的学习使用平台     

Scheduling of Offset Free Systems

In this paper, we study the problem of scheduling hard real-time periodic tasks. We consider independent tasks which are characterized by a period, a hard deadline and a computation time, but where the offsets may be chosen by the scheduling algorithm. We first show that we can restrict the problem by considering non-equivalent offset assignments. More precisely, we show that there are finitely many non-equivalent offset assignments and we propose a method to reduce significantly this number and consider only the minimal number of non-equivalent offset assignments. We then propose an optimal offset assignment rule which considers only the non-equivalent offset assignments. However the number of combinations remains exponential; for this reason, we also propose a nearly optimal algorithm with a more reasonable time complexity.     

Deterministic approximation of marginal probabilities in Bayes nets

Computation of marginal probabilities in Bayes nets is central to numerous reasoning and automatic decision-making systems. This paper presents a deterministic approximation scheme for this hard problem that supplies provably correct bounds by aggregating probability mass in independence-based (IB) assignments. It refines belief updating methods. It approximates posterior probabilities by finding a small number of the highest probability complete (or evidentially supported) assignments. Under certain assumptions, the probability mass in the union of these assignments is sufficient to obtain a good approximation. Such methods are especially useful for highly connected networks. Since IB assignments contain fewer assigned variables, the probability mass in each assignment is greater than in the respective complete assignment. Thus, fewer assignments are sufficient, and a good approximation can be obtained efficiently. Two classes of algorithms for finding high-probability assignments are suggested: best-first heuristic search and a special integer linear program (ILP). Since IB assignments may be overlapping events in probability space, accumulating the mass in a set of assignments may be hard. In the ILP variant, it is easy to avoid the problem by adding equations that prohibit overlap. In the best-first search algorithm, other schemes are necessary, but experimental results suggest that using inclusion-exclusion (potentially exponential-time in the worst case) in the overlap cases is not too expensive for most problem instances     

A study on limited-cycle scheduling problem with multiple periods

This paper considers the optimal arrangement to minimize the total expected risk on limited-cycle scheduling problem with multiple periods. In this paper, first, the multi period problem is systematically classified and modeled. Next, a recursive formula for the total expected risk is presented, and an algorithm for optimal assignments in limited-cycle problems with multiple periods is proposed based on the branch and bound method. In addition, the effectiveness of the proposed algorithm is shown by investigating the calculation time of the computer. Finally, the optimal assignments are studied by numerical experiments and the property useful for the design of a production seat system is found.     

A study on limited-cycle scheduling problem with multiple periods

This paper considers the optimal arrangement to minimize the total expected risk on limited-cycle scheduling problem with multiple periods. In this paper, first, the multi period problem is systematically classified and modeled. Next, a recursive formula for the total expected risk is presented, and an algorithm for optimal assignments in limited-cycle problems with multiple periods is proposed based on the branch and bound method. In addition, the effectiveness of the proposed algorithm is shown by investigating the calculation time of the computer. Finally, the optimal assignments are studied by numerical experiments and the property useful for the design of a production seat system is found.     

Branch-and-bound task allocation with task clustering-based pruning

We propose a task allocation algorithm that aims at finding an optimal task assignment for any parallel programs on a given machine configuration. The theme of the approach is to traverse a state–space tree that enumerates all possible task assignments. The efficiency of the task allocation algorithm comes from that we apply a pruning rule on each traversed state to check whether traversal of a given sub-tree is required by taking advantage of dominance relation and task clustering heuristics. The pruning rules try to eliminate partial assignments that violate the clustering of tasks, but still keeping some optimal assignments in the future search space. In contrast to previous state–space searching methods for task allocation, the proposed pruning rules significantly reduce the time and space required to obtain an optimal assignment and lead the traversal to a near optimal assignment in a small number of states. Experimental evaluation shows that the pruning rules make the state–space searching approach feasible for practical use.     

求解多文字可满足SAT问题的置信传播算法

可满足(SAT)问题是指:是否存在一组布尔变元赋值,使得合取范式公式中每个子句至少有一个文字为真.多文字可满足SAT问题是指:是否存在一组布尔变元赋值,使得CNF公式中每个子句至少有两个文字为真.显然,此问题仍然是一个NP难问题.为了研究解决多文字可满足SAT问题的算法,引入随机实例产生模型,设计求解多文字可满足SAT问题的置信传播算法.最后,用实例模型产生了大量数据进行实验验证,结果表明:该算法求解多文字可满足SAT问题的性能优于其他启发式算法.     

An algorithm for ranking assignments using reoptimization

We consider the problem of ranking assignments according to cost in the classical linear assignment problem. An algorithm partitioning the set of possible assignments, as suggested by Murty, is presented where, for each partition, the optimal assignment is calculated using a new reoptimization technique. Its computational performance is compared with all available implementations of algorithms with the same time complexity. The results are encouraging.     

Distribution of assignments among participants under conditions of constraints

The distribution problem of assignments among participants in the presence of constraints is considered. For each assignment participants are defined, whom this assignment can be transferred to, and participants who cannot take the given assignment. Some collections of assignments are marked as clusters, i.e., all assignments of each such cluster can be given up only to one participant; and clusters can be intersected. Estimates of the extremum are set out, an approximate algorithm of the solution is proposed. The problems of this type can be met with, for example, in multiprocessor computing complexes in the distribution of assignments among processors, in the distribution of jobs among executors, and in a number of other cases.     

一种基于修改的约束满足算法

求解约束满足问题的修改算法从实始的有冲突的完整解出发，不断修改理有的变量赋值，从而得到无冲突的完整解。本文将启发式方法应用了修改型算法，提出了一种高效的基于修改的约束满足算法。     

Distributed constraint satisfaction with partially known constraints

Distributed constraint satisfaction problems (DisCSPs) are composed of agents connected by constraints. The standard model for DisCSP search algorithms uses messages containing assignments of agents. It assumes that constraints are checked by one of the two agents involved in a binary constraint, hence the constraint is fully known to both agents. This paper presents a new DisCSP model in which constraints are kept private and are only partially known to agents. In addition, value assignments can also be kept private to agents and not be circulated in messages. Two versions of a new asynchronous backtracking algorithm that work with partially known constraints (PKC) are presented. One is a two-phase asynchronous backtracking algorithm and the other uses only a single phase. Another new algorithm preserves the privacy of assignments by performing distributed forward-checking (DisFC). We propose to use entropy as quantitative measure for privacy. An extensive experimental evaluation demonstrates a trade-off between preserving privacy and the efficiency of search, among the different algorithms. Partially supported by the Spanish project TIN2006-15387-C03-01. Partially supported by the Lynn and William Frankel center for Computer Sciences and the Paul Ivanier Center for Robotics and Production Management.     

A mathematical approach to large scale personnel assignment

This paper reports on a computer-based system for military personnel assignment. Transportation costs, job skill requirements and individual skills and preferences are manipulated to produce three measures of assignment costs. The weighted combination of these measures is the total cost of each assignment. An algorithm based on the Ford-Fulkerson network flow approach is used to generate the optimal set of assignments by identifying the set which minimizes the total cost of all possible assignments.     

Sensor scheduling in mobile robots using incomplete information via Min-Conflict with Happiness.

This paper develops and applies a variant of the Min-Conflict algorithm to the problem of sensor allocation with incomplete information for mobile robots. A categorization of the types of contention over sensing resources is provided, as well as a taxonomy of available information for the sensor scheduling task. The Min-Conflict with Happiness (MCH) heuristic algorithm, which performs sensor scheduling for situations in which no information is known about future assignments, is then described. The primary contribution of this modification to Min-Conflict is that it permits the optimization of sensor certainty over the set of all active behaviors, thereby producing the best sensing state for the robot at any given time. Data are taken from simulation experiments and runs from a pair of Nomad200 robots using the SFX hybrid deliberative/reactive architecture. Results from these experiments demonstrate that MCH is able to satisfy more sensor assignments (up to 142%) and maintain a higher overall utility of sensing than greedy or random assignments (a 7-24% increase), even in the presence of sensor failures. In addition, MCH supports behavioral sensor fusion allocations. The practical advantages of MCH include fast, dynamic repair of broken schedules allowing it to be used on computationally constrained systems, compatibility with the dominant hybrid robot architectural style, and least-disturbance of prior assignments minimizing interruptions to reactive behaviors.     

Critical Load Factors in Two-Processor Distributed Systems

In a two-processor distributed computer network, prior research showed that a maximum flow algorithm can be used to find optimal program-module-to-processor assignments to maximize the performance of distributed programs. This paper examines the sequence of optimal assignments found as the load on one processor is held fixed and the load on the other is varied. For every program module M there exists a critical load factor fM such that when the load on the processor with variable load is below fM, M is assigned to that processor by an optimal assignment, and is otherwise assigned to the other processor. This characteristic opens the possibility of doing optimal dynamic assignments in real-time.