Abstract:Graph grammars have been developed as an extension of the formal grammars on strings to grammars on graphs, and provide a mechanism in which transformations on graphs can be modeled in a mathematically precise way. In this paper, based on confluent graph grammars, the authors present a novel representation for data-flow graphs, control-flow graphs, combined control-data-graphs, bipartite graphs and hyperedge graphs. How to extract parallelism is specified automatically at different levels by graph rewriting, thus facilitating the design and implementation of parallel compilers and parallel languages.

Abstract:Based on recursive functions defined on context-free language, LFC (language for context free recursive function) is a formal specification language and fits for dealing with phrase structure. LFC is yet another functional language with many general characteristics. It has been implemented in SAQ (specification acquisition system).The original type system for LFC is not polymorphic. With type variables, the original type system can be augmented and become a polymorphic type system. The type checking algorithm and some problems about implementation are also discussed. Polymorphic type system makes LFC more agile and predicts good future in the applications of LFC.

Abstract:Scalability is an important performance criterion of parallel computing. However the conventional scalability metrics are not suitable for SMP(symmetric multiprocessor) cluster. How to measure scalability of SMP cluster? This paper proposes a solution to the problem. It first finds out and verifies the reason, nonequivalence of the processor sets and then it adopts the viewpoint of processor set to observe the behaviors of the system correctly and comprehensively instead of using only the number of processors to describe the parallel system. By introducing the concept of performance reference factor, it extends the conventional metrics to fit the SMP cluster architecture.As the experiments indicate, the extended metrics are applicable to the SMP cluster and have high precision.

Abstract:Software pipelining is a loop optimization technique that has been widely implemented in modern optimizing compilers. In order to fully utilize the instruction level parallelism of the recent VLIW DSP processors, DSP programs have to be optimized by software pipelining. However, because of the transformation of the original sequential code, a software-pipelined loop is often difficult to understand, test, and debug. It is also very difficult to reuse and port a software-pipelined loop to other processors, especially when the original sequential code is unavailable. In this paper we propose a de-pipelining algorithm which converts the optimized assembly code of a software-pipelined loop back to a semantically equivalent sequential counterpart. Preliminary experiments on 20 programs verify the validity of the proposed de-pipelining algorithm.

Abstract:Hypercube multi-computers system is of good performance in parallel and distributed computation. With the increasing size of a multi-computers system, the fault possibility of computers and their links increases. It is very important to seek for better fault-tolerant routing strategies to realize an effective fault-tolerant routing. A novel fault-tolerant routing algorithm in hypercube multi-computers system is proposed, in which each node uses a maximum safety path matrices (MSPMs) to record the optimal paths to the other nodes. It proves that MSPMs can record most of the optimal paths by n-1 rounds of information exchanges between neighboring nodes. Furthermore, it proves that MSPMs is the final extension of the Optimal Path Matrices (OPMs) and the Extended Optimal Path Matrices (EOPMs) which also use the matrices to record the optimal paths in hypercube multi-computers system, so the problem of how to record the most of optimal paths in the n dimensional hypercube multi-computers system by using matrices is solved finally.

Abstract:Software pipelining tries to improve the performance of a loop by overlapping the execution of several successive iterations. Modulo scheduling is a kind of widely used scheduling technique. The drawbacks of software pipelining, such as increased register pressure, would sometimes degrade the performance improvement that software pipelining gains. This kind of cost varies with the processor architecture, compiler optimization, and characteristics of programs. In this paper, a program characteristics oriented cost model for software pipelining is proposed, and the cost is evaluated in some aspects. A dependency based cost testing (DBCT) algorithm is developed to provide information for the compiler to decide whether to apply software pipelining or not. Experimental results show that DBCT algorithm boosts performance greatly.

Abstract:Model checking has being used mainly to check if a system satisfies the specifications expressed in temporal logic and people pay little attention to the model checking problem for logics of knowledge. However, in the distributed systems community, the desirable specifications of systems and protocols have been expressed widely in logics of knowledge. In this paper, the model checking approaches for the temporal logic of knowledge are discussed. On the base of SMV (symbolic model verifier), according to the semantics of knowledge and set theory, several approaches for model checking of knowledge and common knowledge are presented. These approaches make SMV's functions extended from temporal logics to temporal logics of knowledge. They also correspond to other model checking approaches and tools where the output is the set of states.

Abstract:Outliers are data values that lie away from the general clusters of other data values. It may be that an outlier implies the most important feature of a dataset. In this paper, a new fuzzy kernel clustering algorithm is presented to locate the critical areas that are often represented by only a few outliers. Through mercer kernel functions, the data in the original space are firstly mapped to a high-dimensional feature space. Then a modified objective function for fuzzy clustering is introduced in the feature space. An additional weighting factor is assigned to each vector in the feature space, and the weight value is updated using the iterative functions derived from the objective function. The final weight of a datum represents a kind of representativeness of the corresponding datum. With these weights, the experts can identify the outliers easily. The simulations demonstrate the feasibility of this method.

Abstract:A novel theory called bi-default theory is proposed for handling inconsistent knowledge simultaneously in the context of default logic without leading to triviality of the extension. To this end, the positive and negative transformations of propositional formulas are defined such that the semantic link between a literal and its negation is split. Most theorems of default logic can be reproduced in the setting of the bi-default logic. It is proven that the bi-default logic is a generalization of the default logic in the presence of inconsistency. A method is provided as an alternative approach for making the reasoning ability of paraconsistent logic as powerful as the classical one.

Abstract:At present, the method of learning Bayesian network structure with missing data is mainly based on the search and scoring method combined with EM algorithm. The algorithm has low efficiency and easily gets into local optimal structure. In this paper, a new method of learning Bayesian network structure with missing data is presented. First, unobserved data are randomly initialized. As a result, a complete data set is got. Based on the complete data set, the maximum likelihood tree is built as an initialization Bayesian network structure. Second, unobserved data are reassigned by combining Bayesian network with Gibbs sampling. Third, on the basis of the new complete data set, the Bayesian network structure is regulated based on the basic dependency relationship between variables and dependency analysis method. Finally, the second and third steps are iterated until the structure goes stable. This method can avoide the exponential complexity of standard Gibbs sampling and the main problems in the existing algorithm. It provides an effective and applicable method for uncertain knowledge representation, inference, and reasoning with missing data.

Abstract:Fairness is the basic requirement of E-Commerce protocols. RSA is one of the most widely used cryptosystems. A fair-exchange protocol allows two parties to exchange items in a fair way so that either each party gets the other's item, or neither party does. In this paper construction and architecture of the existing fair exchange protocols are analyzed. Both practicality and efficiency problems of these protocols are also presented. Based on this analysis, an optimistic fair exchange protocol totally based on RSA signature scheme is proposed. The novel scheme employs verifiably encrypted RSA signatures in the extended integer ring that is elaborately constructed. The security and efficiency of the newly devised scheme are also proved and examined. It is showed that the proposed scheme is secure and efficient.

Abstract:Storage management is one of the most important problems for the current network storage system. The kernel of solving storage management problem is to self-adapt storage system to all changes of external environment and internal events, and to carry out self-regulation and self-management. The key to storage manageability is self-adaptation. A new method and architecture for implementing storage management is introduced in this paper that is to realize self-adaptation SAN storage management system based on Autonomic Computing theory. On the basis of Tsinghua Mass storage network system project (TH-MSNS),we have produced a common framework of the SAN (storage area network) storage management system, and implemented an adaptive-level Autonomic SAN storage system. Test results show that the new SAN storage system has a better performance than the old system.

Abstract:Grid is a new paradigm of Internet computing to share distributed resources and collaborate among them. A web service-based approach for Grid can improve the extensibility and interoperability of Grid system. In this paper, a layered Grid functional model is discussed; within the OGSA (open grid service architecture) framework, a Web service-based Grid architecture is presented. An approach of integrating web services and Grid technology is proposed. Web service workflow technology is used to model the task of the Grid application and its requirement on resource services. The architecture of a Web service-based Grid supporting environment called WebSASE4G is introduced, which gives a new approach to Web service based Grid architecture.

Abstract:This paper shows a simple, efficient, and practical algorithm for locating all occurrences of a finite number of a finite number of keywords in a char/Chinesw character string allowing k chars inserting errors.The algorithm consists of constructing muleiple finite state single-pattern matching machines form keywords and a state-driver appled to drive all finite state finite state single-pattern matching machines,and then using the state-driver to process the text string in a single pass.Speed of the matching is independentof the amount of the inserting errors.Generally,the text string in a not need to inspect every character of the string.They skip as many characters as possible by making full use of the information in matching failure and text window mechanism.This algorithm can be widely applied to network infomation auditing,database,information retrieval,and etc.

Abstract:Gnutella protocol simply uses flooding algorithm to route peer's querying, so it has the poor scalability problem. For not using down-layer's routing information of Internet, it also has the common problem that its querying routing is just implemented on application layer, and its efficiency is low. The distributions of topology nodes in Gnutella and Internet are reviewed, and they not only exhibit power law and small world properties, but also have the near power-coefficient t. A new distributed peer-to-peer network model based on active network technology (active distributed peer-to-peer network, ADP2PN) is proposed, and its prototype system is implemented. Simulation results about ADP2PN's prototype architecture and querying routing algorithm show that it could effectively resolve the above problems, so the model is reasonable and valid.

Abstract:From the viewpoint of decision theory, AQM (active queue management) can be considered as an optimal decision problem. In this paper, a new AQM scheme, Reinforcement Learning Gradient-Descent (RLGD), is described based on the optimal decision theory of reinforcement learning. Aiming to maximize the throughput and stabilize the queue length, RLGD adjusts the update step adaptively, without the demand of knowing the rate adjustment scheme of the source sender. Simulation demonstrates that RLGD can lead to the convergence of the queue length to the desired value quickly and maintain the oscillation small. The results also show that the RLGD scheme is very robust to disturbance under various network conditions and outperforms the traditional REM and PI controllers significantly.

Abstract:Normalization design of XML Schemas and DTDs (document type definitions) is to produce a set of XML schemas or DTDs that can well represent data dependencies and eliminate redundancies. Now there are a few researches on it, and the existing researches are still at its initial stage. Provost proposed the idea of applying the theory of relational database to XML schemas normalization design. This idea has not been put into practice. The paper shows algorithms of hierarchical schemas design for XML schemas and DTDs normalization design based on Provost's idea. Firstly the paper analyzes hierarchy decomposition based on Provost's idea. Then it presents an algorithm producing a decomposition tree to eliminate redundant schemas. Finally it shows an algorithm of hierarchical schemas design for XML schemas and DTDs normalization design to get over deficiencies for Provost's idea. With respect to other researches on normalization design for XML schemas and DTDs, the set of full and embedded MVDs in hierarchical schemas produced by these algorithms are implied by the given set of MVDs (multivalued dependencies), and the hierarchical schemas eliminate redundant ones and satisfy the lossless join property.