Volume 9,Issue 8,1998 Table of Contents
1998, 9(8):561-365.
Abstract:
Collective communications play an important role in parallel computing. Many features of an ATM(asynchronous transfer mode) switch environment can be exploited in the design of collective operations. In this paper, the authors present a collective communications framework based on ATM——hybrid-tree, which fully takes advantage of the features supporting multicast of ATM and is suitable to implement collective communications in dynamic groups. The problems of the maintance of the hybrid-tree are completely solved by the group management protocol and methods to maintain the hybrid-tree presented in this paper.
Collective communications play an important role in parallel computing. Many features of an ATM(asynchronous transfer mode) switch environment can be exploited in the design of collective operations. In this paper, the authors present a collective communications framework based on ATM——hybrid-tree, which fully takes advantage of the features supporting multicast of ATM and is suitable to implement collective communications in dynamic groups. The problems of the maintance of the hybrid-tree are completely solved by the group management protocol and methods to maintain the hybrid-tree presented in this paper.
1998, 9(8):566-573.
Abstract:
In this paper, the concept of global distributed data sources over WWW(WWWDS) is introduced. A simple and extensible data model based on node, node container, node graph and link points are discussed in details. A powerful SQL-like query language (WWWQL) for WWWDS is introduced and the query processing and optimization technology for WWWQL are discussed as well.
In this paper, the concept of global distributed data sources over WWW(WWWDS) is introduced. A simple and extensible data model based on node, node container, node graph and link points are discussed in details. A powerful SQL-like query language (WWWQL) for WWWDS is introduced and the query processing and optimization technology for WWWQL are discussed as well.
1998, 9(8):574-578.
Abstract:
Novel applications require multicast delivery and group management abilities from communication facilities. For high-speed transmission services and new network layer protocols have already provided some issues interested, research on transport protocols has become a hot topic again both in academy and standardization sectors. The group communication model which the authors get, the projections for lightweight transport protocols XTP and computer conferencing applications are described in this paper.
Novel applications require multicast delivery and group management abilities from communication facilities. For high-speed transmission services and new network layer protocols have already provided some issues interested, research on transport protocols has become a hot topic again both in academy and standardization sectors. The group communication model which the authors get, the projections for lightweight transport protocols XTP and computer conferencing applications are described in this paper.
1998, 9(8):580-585.
Abstract:
The use of the cache reduces the gap between the CPU speed and the memory latency, so the cache hit ratio becomes an important factor which affects the performance of multiprocessor system. Researchers have developed a number of optimizations to enhance data locality, increase the cache hit ratio and bring the multiprocessor system performance into better play. These techniques focus on how to enhance data locality within a parallel loop, reduce and even eliminate the cache line thrashing due to true or false sharing of the cache line. Exploitation and utilization of cross-loop reuse on multiprocessors are seldom discussed. How to exploit and utilize these cross-loop reuse, and put forward some feasible and easy ways for implementation are discussed in this paper. Application of these methods can effectively increase the cache hit ratio, thus improve the performance of multiprocessor system.
The use of the cache reduces the gap between the CPU speed and the memory latency, so the cache hit ratio becomes an important factor which affects the performance of multiprocessor system. Researchers have developed a number of optimizations to enhance data locality, increase the cache hit ratio and bring the multiprocessor system performance into better play. These techniques focus on how to enhance data locality within a parallel loop, reduce and even eliminate the cache line thrashing due to true or false sharing of the cache line. Exploitation and utilization of cross-loop reuse on multiprocessors are seldom discussed. How to exploit and utilize these cross-loop reuse, and put forward some feasible and easy ways for implementation are discussed in this paper. Application of these methods can effectively increase the cache hit ratio, thus improve the performance of multiprocessor system.
1998, 9(8):586-591.
Abstract:
In this paper, a concurrent object-oriented programming model is presented. It consists of a group of concurrent objects which may have bodies. When the concurrent object with a body is created, its body begin to run. In this model, the synchronous message passing is adopted for inter-object communication and the intra-object concurrency is permitted. The object concurrency control is distributed among each method's activation condition in an object. Based on the presented model, C++ is extended. A policy is also given to transform the classes defined in the extended C++ into C++ classes. The implementation uses the multithreading and synchronization mechanisms supported in some multitasking operating systems, such as Windows 95.
In this paper, a concurrent object-oriented programming model is presented. It consists of a group of concurrent objects which may have bodies. When the concurrent object with a body is created, its body begin to run. In this model, the synchronous message passing is adopted for inter-object communication and the intra-object concurrency is permitted. The object concurrency control is distributed among each method's activation condition in an object. Based on the presented model, C++ is extended. A policy is also given to transform the classes defined in the extended C++ into C++ classes. The implementation uses the multithreading and synchronization mechanisms supported in some multitasking operating systems, such as Windows 95.
1998, 9(8):592-597.
Abstract:
The research of parsing is important in the field of natural language processing. An efficient stochastic context-free parsing algorithm is described in this paper. In order to implement a stochastic context-free parser, the authors rebuild a GLR-algorithm-like parsing table so that derivation probabilities can be computed efficiently by making use of the parsing control structure, and add indices to each state in parsing period as identifiers of different parsing paths. Based on the techniques above, the forward and inner probabilities of states are introduced in this paper. With these two probabilities, the probabilities of all parsing trees of the input sentence can be computed to select an optimal parsing result. The experiment shows that the proposed algorithm is efficient.
The research of parsing is important in the field of natural language processing. An efficient stochastic context-free parsing algorithm is described in this paper. In order to implement a stochastic context-free parser, the authors rebuild a GLR-algorithm-like parsing table so that derivation probabilities can be computed efficiently by making use of the parsing control structure, and add indices to each state in parsing period as identifiers of different parsing paths. Based on the techniques above, the forward and inner probabilities of states are introduced in this paper. With these two probabilities, the probabilities of all parsing trees of the input sentence can be computed to select an optimal parsing result. The experiment shows that the proposed algorithm is efficient.
1998, 9(8):598-600.
Abstract:
In this paper, the author discusses constraint satisfaction problems in the framework of first-order logic. Local search methods for satisfying first-order formulas are studied, and compared with satisfiability procedures in the propositional logic. Experimental results on the Queens problem and the Hamiltanian circuit problem show that the framework is suitable for dealing with quite large problem instances.
In this paper, the author discusses constraint satisfaction problems in the framework of first-order logic. Local search methods for satisfying first-order formulas are studied, and compared with satisfiability procedures in the propositional logic. Experimental results on the Queens problem and the Hamiltanian circuit problem show that the framework is suitable for dealing with quite large problem instances.
1998, 9(8):601-605.
Abstract:
In this paper, the author introduces the design and implementation of an interactive procedure for grammatical inference. It serves as a tool to help the users acquire concepts represented as context-free grammars from finite examples and sentential forms, which some known concepts can be reused as sub-concepts.
In this paper, the author introduces the design and implementation of an interactive procedure for grammatical inference. It serves as a tool to help the users acquire concepts represented as context-free grammars from finite examples and sentential forms, which some known concepts can be reused as sub-concepts.
1998, 9(8):606-608.
Abstract:
When Internet is becoming the popular highway for information exchange, the domain of applications and the types of client software are diversifying. Thus the integration of database with Internet is becoming an imminent research issue as most data in computer are managed by DBMS and the amount of data managed by DBMS is huge. But the modern DBMSs do not support connection to Internet. And the applications based on those DBMSs will become legacy system in the future. In this paper, the authors introduce the design of database information dissemination on Internet in TCPIMS project and describe the information model based on WWW-View and the rebuilding tools based on script input file.
When Internet is becoming the popular highway for information exchange, the domain of applications and the types of client software are diversifying. Thus the integration of database with Internet is becoming an imminent research issue as most data in computer are managed by DBMS and the amount of data managed by DBMS is huge. But the modern DBMSs do not support connection to Internet. And the applications based on those DBMSs will become legacy system in the future. In this paper, the authors introduce the design of database information dissemination on Internet in TCPIMS project and describe the information model based on WWW-View and the rebuilding tools based on script input file.
1998, 9(8):609-612.
Abstract:
Some of the research work which the authors have done on microkernel in the last 5 years are described in this paper. Three new algorithms have been proposed. The first algorithm combines task schedule and thread schedule algorithms together to improve the efficiency of the thread schedule system, it also provides a more fairness scheduling algorithm for microkernel operating system. The second algorithm is an enhanced copy－on－write algorithm, it combines copy －on－write and copy－on－reference algorithms together to make it more suitable on I386 architecture. The last algorithm is a new timing algorithm for microkernel operating system, it solves the inaccuracy timing problem which is caused by traditional timing algorithm running under the microkernel architecture.
Some of the research work which the authors have done on microkernel in the last 5 years are described in this paper. Three new algorithms have been proposed. The first algorithm combines task schedule and thread schedule algorithms together to improve the efficiency of the thread schedule system, it also provides a more fairness scheduling algorithm for microkernel operating system. The second algorithm is an enhanced copy－on－write algorithm, it combines copy －on－write and copy－on－reference algorithms together to make it more suitable on I386 architecture. The last algorithm is a new timing algorithm for microkernel operating system, it solves the inaccuracy timing problem which is caused by traditional timing algorithm running under the microkernel architecture.
1998, 9(8):613-618.
Abstract:
The MBMS(model base management system) is the kernel of a DSS(decision support system). The authors introduce the design and implementation of a client/server model base management system that runs on a heterogeneous distributed environment in this paper. In this system, a model is viewed as a program module and defined by a model IDL(interface definition language). By being organized with object oriented method and supporting remote and dynamic function (model) invocation transparently, the DSS may be developed easily and have very good static and dynamic extensibility. Also since many semantic information have been stored in the model base, the authors may develop more tools based on it to support the DSS development process.
The MBMS(model base management system) is the kernel of a DSS(decision support system). The authors introduce the design and implementation of a client/server model base management system that runs on a heterogeneous distributed environment in this paper. In this system, a model is viewed as a program module and defined by a model IDL(interface definition language). By being organized with object oriented method and supporting remote and dynamic function (model) invocation transparently, the DSS may be developed easily and have very good static and dynamic extensibility. Also since many semantic information have been stored in the model base, the authors may develop more tools based on it to support the DSS development process.
1998, 9(8):619-621.
Abstract:
Two kinds of composition Petri nets are proposed in order to analyze the properties of a complicated nets. The condition for reserving structural properties of Petri net after composition are discussed. These results provide new methods for synthesis and analysis of P/T nets.
Two kinds of composition Petri nets are proposed in order to analyze the properties of a complicated nets. The condition for reserving structural properties of Petri net after composition are discussed. These results provide new methods for synthesis and analysis of P/T nets.
1998, 9(8):622-627.
Abstract:
Constraint satisfaction problems occur widely in artificial intelligence. Hence, arc consistency techniques have been widely studied to simplify constraint networks before or during the search for solutions. To reduce the cost of maintenance, the researchers have focused their work on the improvement of maintaining a single arc consistency. In this paper, from a higher point of view, the authors try to propose some principles and the corresponding strategies of three levels, which are search level, maintenance level and arc level. In this way, MAC-Dynamic and AC-I+ are presented. The effectiveness of this approach is demonstrated experimentally on two typical benchmarks of CSPs: Zebra Puzzles and N-Queen Problem.
Constraint satisfaction problems occur widely in artificial intelligence. Hence, arc consistency techniques have been widely studied to simplify constraint networks before or during the search for solutions. To reduce the cost of maintenance, the researchers have focused their work on the improvement of maintaining a single arc consistency. In this paper, from a higher point of view, the authors try to propose some principles and the corresponding strategies of three levels, which are search level, maintenance level and arc level. In this way, MAC-Dynamic and AC-I+ are presented. The effectiveness of this approach is demonstrated experimentally on two typical benchmarks of CSPs: Zebra Puzzles and N-Queen Problem.
1998, 9(8):628-631.
Abstract:
A parallel scheduler for distributed system is described. This scheduler uses a data-structure AT(assignment table) to record the tasks' dynamic characteristics, and schedules processors by an algorithm DRA(dynamic readjusting algorithm). This paper shows that the capacity of the distributed system is improved.
A parallel scheduler for distributed system is described. This scheduler uses a data-structure AT(assignment table) to record the tasks' dynamic characteristics, and schedules processors by an algorithm DRA(dynamic readjusting algorithm). This paper shows that the capacity of the distributed system is improved.
1998, 9(8):632-636.
Abstract:
In this paper, the author first introduces the concept of hash high order dictionary, and then presents a data compression model using hash high order dictionary. The experiment results show that the model has more power ability to compression data.
In this paper, the author first introduces the concept of hash high order dictionary, and then presents a data compression model using hash high order dictionary. The experiment results show that the model has more power ability to compression data.
1998, 9(8):637-640.
Abstract:
The authors present a learning algorithm of decision tree generation for interval-valued attributes. With regard to range of value, a nominal attribute is not ordered and a continuous-valued attribute is linearly ordered, but the interval-valued attribute is partially ordered. As a generalization of ID3-algorithm on intervals, this algorithm uses minimal information entropy of partitioning to select the extended attributes. The efficiency of the algorithm is improved by analyzing unstable cut points.
The authors present a learning algorithm of decision tree generation for interval-valued attributes. With regard to range of value, a nominal attribute is not ordered and a continuous-valued attribute is linearly ordered, but the interval-valued attribute is partially ordered. As a generalization of ID3-algorithm on intervals, this algorithm uses minimal information entropy of partitioning to select the extended attributes. The efficiency of the algorithm is improved by analyzing unstable cut points.
联系方式
- 《Journal of Software 》
- 主办单位：Institute of Software, CAS, China
- 邮编：100190
- 电话：010-62562563
- 电子邮箱：jos@iscas.ac.cn
- 网址：https://www.jos.org.cn
- 刊号：ISSN 1000-9825
- CN 11-2560/TP
- 国内定价：70元
You are the firstVisitors
Copyright: Institute of Software, Chinese Academy of Sciences Beijing ICP No. 05046678-4
Address：4# South Fourth Street, Zhong Guan Cun, Beijing 100190,Postal Code：100190
Phone：010-62562563 Fax：010-62562533 Email：jos@iscas.ac.cn
Technical Support：Beijing Qinyun Technology Development Co., Ltd.
Copyright: Institute of Software, Chinese Academy of Sciences Beijing ICP No. 05046678-4
Address：4# South Fourth Street, Zhong Guan Cun, Beijing 100190,Postal Code：100190
Phone：010-62562563 Fax：010-62562533 Email：jos@iscas.ac.cn
Technical Support：Beijing Qinyun Technology Development Co., Ltd.
